# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
159140 | 2019-10-21T08:12:28 Z | nafis_shifat | Split the sequence (APIO14_sequence) | C++11 | 2000 ms | 17040 KB |
#include<bits/stdc++.h> #define pii pair<int,int> #define ll long long using namespace std; const ll inf=1e15; int main() { int n,k; cin>>n>>k; ll dp[n+10][k+10]={}; ll a[n+5]={}; ll cum1[n+5]={}; ll cum2[n+5]={}; for(int i=1;i<=n;i++) { cin>>a[i]; cum1[i]=cum1[i-1]+a[i]; } for(int i=n;i>0;i--)cum2[i]=cum2[i+1]+a[i]; for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=0; for(int i=0;i<=n;i++) { dp[i][0]=0; dp[i][1]=cum1[i]*cum2[i+1]; } for(int i=1;i<n;i++) { for(int j=2;j<=k && j<=i;j++) { int r=i-1; int l=j-1; int p=0; if(l==r) { dp[i][j]=dp[i-1][j-1]+(cum1[i]-cum1[i-1])*cum2[i+1]; continue; } while(r>=l) { int mid1 = l+(r-l)/3; int mid2 = r-(r-l)/3; if(dp[mid1][j-1]+(cum1[i]-cum1[mid1])*cum2[i+1]>dp[mid2][j-1]+(cum1[i]-cum1[mid2])*cum2[i+1]) { r=mid2-1; p=mid1; } else { p=mid2; l=mid1+1; } } //cout<<i<<" "<<j<<endl; dp[i][j]=dp[p][j-1]+(cum1[i]-cum1[p])*cum2[i+1]; } } ll mx=0,st; for(int i=1;i<=n;i++) { if(dp[i][k]>mx) { mx=dp[i][k]; st=i; } } cout<<mx<<endl; int cur=mx; cout<<st<<" "; int d=1; while(k>1) { for(int i=st-1;i>0;i--) { if(dp[i][k-1]+(cum1[st]-cum1[i])*cum2[st+1]==cur) { cur=dp[i][k-1]; cout<<i<<" "; st=i; k--; } } } //for(int i=1;i<=10;i++)cout<<dp[i][3]+(cum1[11]-cum1[i])*cum2[12]<<" "<<dp[i][3]<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 999 == 999 |
3 | Incorrect | 2 ms | 256 KB | Integer 5212286 violates the range [1, 1] |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Correct | 2 ms | 256 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Execution timed out | 2053 ms | 376 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 311760000 == 311760000 |
3 | Execution timed out | 2056 ms | 632 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 21503404 == 21503404 |
2 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 140412195 == 140412195 |
3 | Execution timed out | 2053 ms | 2060 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1528 KB | contestant found the optimal answer: 1818678304 == 1818678304 |
2 | Correct | 8 ms | 1528 KB | contestant found the optimal answer: 1326260195 == 1326260195 |
3 | Execution timed out | 2051 ms | 17040 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2055 ms | 12796 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |