Submission #1818754
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(1<<18);
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:28:15+0900
Task
E - 天下一合体
User
TangentDay
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2802 Byte
Status
RE
Exec Time
642 ms
Memory
21504 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
3 ms
4352 KB
example1
RE
272 ms
4352 KB
example2
RE
99 ms
4352 KB
fix0
AC
609 ms
21504 KB
fix1
AC
609 ms
21504 KB
fix2
AC
606 ms
21504 KB
lis0
AC
580 ms
21504 KB
lis1
AC
583 ms
21504 KB
maxrand0
AC
633 ms
21504 KB
maxrand1
AC
642 ms
21504 KB
smallrand0
AC
3 ms
4352 KB
smallrand1
AC
4 ms
4352 KB
smallrand2
AC
3 ms
4352 KB
smallrand3
AC
3 ms
4352 KB
smallrand4
RE
101 ms
4352 KB
smallrand5
RE
99 ms
4352 KB
smallrand6
AC
3 ms
4352 KB
smallrand7
AC
3 ms
4352 KB
smallrand8
RE
100 ms
4352 KB
smallrand9
AC
4 ms
4352 KB
zero0
AC
612 ms
21504 KB
zero1
AC
611 ms
21504 KB
zero2
AC
608 ms
21504 KB
zero3
AC
611 ms
21504 KB
zero4
AC
608 ms
21504 KB
zeromed0
AC
7 ms
4608 KB
zeromed1
AC
6 ms
4608 KB
zeromed2
AC
4 ms
4480 KB
zeromed3
RE
105 ms
4608 KB
zeromed4
RE
106 ms
4608 KB
zeroone0
AC
4 ms
4480 KB