Submission #1818758
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;
sg1.init(n+1);
SegmentTree sg2;
sg2.init(n+1);
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:32:55+0900
Task
E - 天下一合体
User
TangentDay
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2863 Byte
Status
RE
Exec Time
631 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
96 ms
256 KB
example2
RE
97 ms
256 KB
fix0
AC
594 ms
18432 KB
fix1
AC
593 ms
18432 KB
fix2
AC
593 ms
18432 KB
lis0
AC
570 ms
18432 KB
lis1
AC
569 ms
18432 KB
maxrand0
AC
617 ms
18432 KB
maxrand1
AC
631 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
96 ms
256 KB
smallrand5
RE
97 ms
256 KB
smallrand6
AC
1 ms
256 KB
smallrand7
AC
1 ms
256 KB
smallrand8
RE
96 ms
256 KB
smallrand9
AC
1 ms
256 KB
zero0
AC
599 ms
18432 KB
zero1
AC
597 ms
18432 KB
zero2
AC
592 ms
18432 KB
zero3
AC
597 ms
18432 KB
zero4
AC
595 ms
18432 KB
zeromed0
AC
4 ms
512 KB
zeromed1
AC
5 ms
512 KB
zeromed2
AC
2 ms
384 KB
zeromed3
RE
101 ms
512 KB
zeromed4
RE
101 ms
640 KB
zeroone0
AC
2 ms
512 KB