# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
477485 | 2021-10-02T09:27:24 Z | PiejanVDC | Split the sequence (APIO14_sequence) | C++17 | 2000 ms | 16024 KB |
#include <bits/stdc++.h> using namespace std; signed main() { int n,k; cin>>n>>k; vector<int>pref(n+1); pref[0]=0; for(int i = 0 ; i < n ; i++) { int x; cin>>x; pref[i+1] = pref[i] + x; } int res[n+1][k+1]; int dp[n+1][k+1]; for(int i = 0 ; i <= n ; i++) dp[i][0] = 0; for(int i = 1 ; i <= k ; i++) dp[0][i] = 0; for(int i = 1 ; i <= k ; i++) { for(int j = 1 ; j <= n ; j++) { dp[j][i] = 0; for(int c = 1 ; c < j ; c++) { if(dp[c][i-1] + (pref[n] - pref[j-1]) * (pref[j-1] - pref[c-1]) > dp[j][i]) { res[j][i] = c; } dp[j][i] = max(dp[j][i],dp[c][i-1] + (pref[n] - pref[j-1]) * (pref[j-1] - pref[c-1])); } } } int mx=0; int node; for(int i = 0 ; i <= n ; i++) { if(dp[i][k] > mx) { mx=dp[i][k]; node = i; } } cout << mx << "\n"; for(int i = 0 ; i < k ; i++) { cout << node-1 << " "; node = res[node][k - i]; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 999 == 999 |
3 | Runtime error | 1 ms | 332 KB | Execution killed with signal 11 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Incorrect | 0 ms | 204 KB | Integer 0 violates the range [1, 49] |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Correct | 1 ms | 204 KB | contestant found the optimal answer: 311760000 == 311760000 |
3 | Incorrect | 8 ms | 588 KB | Integer 0 violates the range [1, 199] |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 316 KB | contestant found the optimal answer: 21503404 == 21503404 |
2 | Correct | 3 ms | 204 KB | contestant found the optimal answer: 140412195 == 140412195 |
3 | Incorrect | 170 ms | 1740 KB | Integer -1 violates the range [1, 999] |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 310 ms | 616 KB | contestant found the optimal answer: 1818678304 == 1818678304 |
2 | Correct | 254 ms | 612 KB | contestant found the optimal answer: 1326260195 == 1326260195 |
3 | Execution timed out | 2059 ms | 16024 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2090 ms | 3788 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |