Submission #1818755
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<<19);
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:58+0900
Task
E - 天下一合体
User
TangentDay
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2802 Byte
Status
RE
Exec Time
643 ms
Memory
27648 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
4 ms
8448 KB
example1
RE
120 ms
8448 KB
example2
RE
103 ms
8448 KB
fix0
AC
613 ms
25600 KB
fix1
AC
611 ms
25600 KB
fix2
AC
609 ms
25600 KB
lis0
AC
584 ms
25600 KB
lis1
AC
585 ms
25600 KB
maxrand0
AC
634 ms
25600 KB
maxrand1
AC
643 ms
25600 KB
smallrand0
AC
4 ms
8448 KB
smallrand1
AC
4 ms
8448 KB
smallrand2
AC
4 ms
8448 KB
smallrand3
AC
4 ms
8448 KB
smallrand4
RE
99 ms
8448 KB
smallrand5
RE
101 ms
8448 KB
smallrand6
AC
4 ms
8448 KB
smallrand7
AC
4 ms
8448 KB
smallrand8
RE
99 ms
8448 KB
smallrand9
AC
4 ms
8448 KB
zero0
AC
614 ms
25600 KB
zero1
AC
614 ms
27648 KB
zero2
AC
609 ms
25600 KB
zero3
AC
612 ms
25600 KB
zero4
AC
612 ms
25600 KB
zeromed0
AC
7 ms
8704 KB
zeromed1
AC
8 ms
8704 KB
zeromed2
AC
5 ms
8576 KB
zeromed3
RE
104 ms
8704 KB
zeromed4
RE
105 ms
8704 KB
zeroone0
AC
5 ms
8576 KB