# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
756555 | Username4132 | Split the sequence (APIO14_sequence) | C++14 | 17 ms | 4528 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<deque>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define F first
#define S second
const int MAXN=100010;
const ll INF=2000000000;
int n, k, arr[MAXN], bck[210][MAXN], ord[MAXN];
ll ans[2][MAXN];
ll sum[MAXN];
bool cw(pll a, pll b, pll c){
return (b.S - a.S)*(c.F - b.F) <= (c.S - b.S)*(b.F - a.F);
}
void opt(int val){
int ind=val&1;
deque<pll> hull;
ans[ind^1][0]=-INF;
int cnt=0;
forn(i, n){
pll pt = {sum[i+1], ans[ind][i]-((ll)sum[i+1])*sum[i+1]};
while(hull.size()>1 && cw(hull[hull.size()-2], hull.back(), pt)) hull.pop_back();
hull.push_back(pt);
if(i==n-1) break;
while(hull.size()>1){
pll perp = {hull[0].S - hull[1].S, hull[1].F - hull[0].F};
if(sum[i+2]*perp.S<perp.F) break;
hull.pop_front();
cnt++;
}
ans[ind^1][i+1] = sum[i+2]*hull.front().F + hull.front().S;
bck[val+1][i+1]=cnt;
}
}
int main(){
scanf("%d %d", &n, &k);
forn(i, n) scanf("%d", arr+i), sum[i+1]=sum[i]+arr[i];
forn(i, k) opt(i);
printf("%lld\n", ans[k&1][n-1]);
int pos=n-1;
forn(i, k){
pos=bck[k-i][pos];
ord[k-i-1]=pos+1;
}
forn(i, k) printf("%d ", ord[i]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |