# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
337134 | 2020-12-18T15:20:00 Z | bigDuck | Split the sequence (APIO14_sequence) | C++14 | 48 ms | 6764 KB |
#include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount int t, n, m, k, a[300010], q, l, r; int dp[1010][210]; int p[1010]; int dir[1010][210]; vector<int> v; int32_t main(){ INIT scanf("%d", &n); scanf("%d" , &k); for(int i=1; i<=n ;i++){ scanf("%d", &a[i]); p[i]=p[i-1]+a[i]; } dp[0][0]=0; k++; for(int i=1; i<=n; i++){ for(int g=0; g<=k; g++){ dp[i][g]=-1; } for(int j=i-1; j>=0; j--){ for(int g=0; g<k; g++){ if(dp[j][g]==-1){continue;} if(dp[i][g+1]==(-1)){ dp[i][g+1]=dp[j][g]+(p[i]-p[j])*(p[i]-p[j]); dir[i][g+1]=j; } else{ if( (dp[j][g]+(p[i]-p[j])*(p[i]-p[j]))<dp[i][g+1] ){ dir[i][g+1]=j; } dp[i][g+1]=min(dp[i][g+1], dp[j][g]+(p[i]-p[j])*(p[i]-p[j])); } } } } cout<<( ((p[n]*p[n])-dp[n][k])/2 ); cout<<"\n"; int cnt=1, cr=n; while(cnt<k){ v.pb(dir[cr][k-cnt+1]); cnt++; cr=dir[cr][k-cnt+1]; } for(int i=k-1-1; i>=0; i--){ cout<<v[i]<<" "; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 1 ms | 364 KB | contestant found the optimal answer: 999 == 999 |
3 | Correct | 1 ms | 364 KB | contestant found the optimal answer: 0 == 0 |
4 | Correct | 1 ms | 364 KB | contestant found the optimal answer: 1542524 == 1542524 |
5 | Incorrect | 1 ms | 364 KB | Integer 0 violates the range [1, 9] |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 492 KB | declared answer doesn't correspond to the split scheme: declared = 1093956, real = 1093884 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 620 KB | declared answer doesn't correspond to the split scheme: declared = 610590000, real = 514120000 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 2028 KB | declared answer doesn't correspond to the split scheme: declared = 21503404, real = 21475184 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 46 ms | 6764 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 | 48 ms | 6764 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |