# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
36858 | 2017-12-16T07:13:24 Z | ae04071 | Split the sequence (APIO14_sequence) | C++11 | 0 ms | 1008 KB |
#include <cstdio> #include <algorithm> #include <vector> #include <assert.h> using namespace std; typedef long long lli; int n,k; lli arr[100001],psum[100001],cache[100001][201],pr[100001][201]; lli a[100001],b[100001]; int pi[100001],sz,si; vector<int> res; bool inter() { lli le = (b[sz-1]-b[sz-2])*(a[sz-1]-a[sz]); lli ri = (b[sz]-b[sz-1])*(a[sz-2]-a[sz-1]); return le>=ri; } void push(int i,int j) { if(sz!=0 && a[sz-1]==psum[i]) { lli bb=cache[i][j] - psum[i] * psum[i]; if(bb>b[sz-1]) { b[sz-1] = bb; pi[sz-1] = i; } return; } a[sz] = psum[i]; b[sz] = cache[i][j] - psum[i] * psum[i]; pi[sz] = i; while(sz-2>=si) { if(!inter()) break; a[sz-1] = a[sz]; b[sz-1] = b[sz]; pi[sz-1] = pi[sz]; sz--; } sz++; } void comp(int i) { while(si+1<sz) { lli lv = a[si]*psum[i] + b[si]; lli rv = a[si+1]*psum[i] + b[si+1]; if(lv<=rv) si++; else break; } } void trace(int i,int j) { if(j==0) return; else { trace(pr[i][j],j-1); res.push_back(pr[i][j]); } } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%lld",arr+i); psum[i]=psum[i-1]+arr[i]; } for(int t=1;t<=k;t++) { sz=si=0; push(t,t-1); for(int i=t+1;i<=n;i++) { comp(i); cache[i][t] = a[si]*psum[i] + b[si]; pr[i][t] = pi[si]; push(i,t-1); } } printf("%lld\n",cache[n][k]); trace(n,k); for(int i=0;i<res.size();i++) printf("%d ",res[i]); sort(res.begin(),res.end()); res.erase(unique(res.begin(),res.end()),res.end()); assert((int)res.size() == k); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 0 ms | 1008 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 0 ms | 1008 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 0 ms | 1008 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 0 ms | 1008 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 0 ms | 1008 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 0 ms | 1008 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |