Submission #1818759
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{
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);
}
};
ll dp[100001][101];
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;
REP(i,n) dp[i+1][0] = INF;
SegmentTree sg1, sg2;
sg1.init(n+1);
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:37:28+0900
Task
E - 天下一合体
User
TangentDay
Language
C++14 (GCC 5.4.1)
Score
900
Code Size
2881 Byte
Status
AC
Exec Time
617 ms
Memory
18304 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:72: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
900 / 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
AC
1 ms
256 KB
example2
AC
1 ms
256 KB
fix0
AC
584 ms
18304 KB
fix1
AC
582 ms
18304 KB
fix2
AC
579 ms
18304 KB
lis0
AC
549 ms
18304 KB
lis1
AC
552 ms
18304 KB
maxrand0
AC
602 ms
18304 KB
maxrand1
AC
617 ms
18304 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
AC
1 ms
256 KB
smallrand5
AC
1 ms
256 KB
smallrand6
AC
1 ms
256 KB
smallrand7
AC
1 ms
256 KB
smallrand8
AC
1 ms
256 KB
smallrand9
AC
1 ms
256 KB
zero0
AC
588 ms
18304 KB
zero1
AC
585 ms
18304 KB
zero2
AC
580 ms
18304 KB
zero3
AC
582 ms
18304 KB
zero4
AC
582 ms
18304 KB
zeromed0
AC
5 ms
1664 KB
zeromed1
AC
5 ms
1280 KB
zeromed2
AC
2 ms
1280 KB
zeromed3
AC
5 ms
1280 KB
zeromed4
AC
7 ms
1664 KB
zeroone0
AC
2 ms
1664 KB