Submission #1818756
Source Code Expand
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll INF = 1e17;
struct SegmentTree{
const ll INF = 1e17;
int n, width;
VL dat;
void init(int x){
n = x;
width = 1;
while (width < n) width *= 2;
dat.resize(2*width-1);
REP(i,2*width-1) dat[i] = INF;
}
void update(int i, ll x){
i += width - 1;
dat[i] = x;
while (i > 0){
i = (i - 1) / 2;
dat[i] = min(dat[i*2+1], dat[i*2+2]);
}
}
ll query(int a, int b, int k, int l, int r){
if (r <= a || b <= l) return INF;
if (a <= l && r <= b) return dat[k];
ll vl = query(a, b, k*2+1, l, (l+r)/2);
ll vr = query(a, b, k*2+2, (l+r)/2, r);
return min(vl, vr);
}
// [l, r)
ll query(int l, int r){
return query(l, r, 0, 0, width);
}
};
int main() {
int n, m;
cin >> n >> m;
VL a(n);
REP(i,n) scanf("%lld", &a[i]);
VL s(n+1);
REP(i,n) s[i+1] = s[i] + a[i];
vector<PL> p(n+1);
REP(i,n+1) p[i] = PL(s[i], i);
sort(ALL(p));
VI pos(n+1);
REP(i,n+1) pos[i] = p[i].second;
// REP(i,n+1) cout << s[i] << " ";
// cout << endl;
// REP(i,n+1) cout << pos[i] << " ";
// cout << endl;
VVL dp(n+1, VL(m, INF));
dp[0][0] = 0;
SegmentTree sg1, sg2;
REP(k,m){
sg1.init(n+1);
sg2.init(n+1);
REP(i,n+1) sg1.update(i, dp[i][k] + s[i]);
// REP(i,n+1) cout << sg1.query(i, i+1) << " ";
// cout << endl;
REP(i,n+1){
// REP(j,n+1) cout << sg1.query(j, j+1) << " ";
// cout << endl;
// REP(j,n+1) cout << sg2.query(j, j+1) << " ";
// cout << endl << endl;
int p = pos[i];
// cout << p << endl;
dp[p][k+1] = min(sg1.query(0, p) - s[p], sg2.query(0, p) + s[p]);
sg1.update(p, INF);
sg2.update(p, dp[p][k] - s[p]);
}
}
// cout << endl;
// REP(k,m+1){
// REP(i,n+1) cout << dp[i][k] << " ";
// cout << endl;
// }
cout << dp[n][m] << endl;
return 0;
}
Submission Info
Submission Time
2017-12-01 03:29:33+0900
Task
E - 天下一合体
User
TangentDay
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2806 Byte
Status
RE
Exec Time
641 ms
Memory
18432 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:71:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i,n) scanf("%lld", &a[i]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 900
Status
Set Name
Test Cases
Sample
example0, example1, example2
All
example0, example1, example2, fix0, fix1, fix2, lis0, lis1, maxrand0, maxrand1, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4, smallrand5, smallrand6, smallrand7, smallrand8, smallrand9, zero0, zero1, zero2, zero3, zero4, zeromed0, zeromed1, zeromed2, zeromed3, zeromed4, zeroone0
Case Name
Status
Exec Time
Memory
example0
AC
1 ms
256 KB
example1
RE
97 ms
256 KB
example2
RE
98 ms
256 KB
fix0
AC
604 ms
18432 KB
fix1
AC
604 ms
18432 KB
fix2
AC
602 ms
18432 KB
lis0
AC
577 ms
18432 KB
lis1
AC
578 ms
18432 KB
maxrand0
AC
628 ms
18432 KB
maxrand1
AC
641 ms
18432 KB
smallrand0
AC
1 ms
256 KB
smallrand1
AC
1 ms
256 KB
smallrand2
AC
1 ms
256 KB
smallrand3
AC
1 ms
256 KB
smallrand4
RE
98 ms
256 KB
smallrand5
RE
97 ms
256 KB
smallrand6
AC
1 ms
256 KB
smallrand7
AC
1 ms
256 KB
smallrand8
RE
98 ms
256 KB
smallrand9
AC
1 ms
256 KB
zero0
AC
609 ms
18432 KB
zero1
AC
608 ms
18432 KB
zero2
AC
606 ms
18432 KB
zero3
AC
606 ms
18432 KB
zero4
AC
605 ms
18432 KB
zeromed0
AC
4 ms
512 KB
zeromed1
AC
5 ms
512 KB
zeromed2
AC
2 ms
384 KB
zeromed3
RE
102 ms
512 KB
zeromed4
RE
103 ms
640 KB
zeroone0
AC
2 ms
512 KB