# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
135096 | 2019-07-23T16:00:22 Z | CaroLinda | Split the sequence (APIO14_sequence) | C++14 | 7 ms | 888 KB |
#include <bits/stdc++.h> #define lp(i,a,b) for(int i=a;i<b;i++) #define pii pair<int,int> #define ll long long #define ff first #define ss second #define pb push_back #define mk make_pair const ll inf = 1e15 ; const int MAXN = 210 ; const int MAXK = 210 ; using namespace std ; int n , k ; ll pref[MAXN] , dp[MAXN][MAXK] ; int cut[MAXN][MAXK] ; vector<int> ans ; ll get(int i , int j) { return pref[j] - pref[i-1] ; } void buildAns(int ini, int c) { if(c==0) return ; ans.pb( cut[ini][c] ) ; buildAns(cut[ini][c]+1,c-1) ; } int main() { scanf("%d%d", &n , &k ) ; lp(i,1,n+1) scanf("%lld", &pref[i] ) ; lp(i,1,n+1) pref[i] += pref[i-1] ; for(int c = 1 ; c <= k ; c++) { for(int i = n ; i > 0 ; i-- ) { if( n - i < c ) { dp[i][c] = -inf ; continue ; } for(int j = i ; j < n ; j++ ) { ll ganho = dp[j+1][c-1] + get(i,j)*get(j+1,n) ; if(ganho > dp[i][c]) cut[i][c] = j , dp[i][c] = ganho ; } } } buildAns(1,k) ; printf("%lld\n" , dp[1][k]); lp(i,0,k) printf("%d ", ans[i]) ; printf("\n"); }
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 | 376 KB | Integer 0 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 | 504 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Correct | 2 ms | 380 KB | contestant found the optimal answer: 122453454361 == 122453454361 |
4 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 93663683509 == 93663683509 |
5 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 1005304678 == 1005304678 |
6 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 933702 == 933702 |
7 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 25082842857 == 25082842857 |
8 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 687136 == 687136 |
9 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 27295930079 == 27295930079 |
10 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 29000419931 == 29000419931 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 764 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Correct | 3 ms | 888 KB | contestant found the optimal answer: 311760000 == 311760000 |
3 | Correct | 6 ms | 888 KB | contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 | Correct | 3 ms | 784 KB | contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 | Correct | 6 ms | 888 KB | contestant found the optimal answer: 1019625819 == 1019625819 |
6 | Correct | 7 ms | 760 KB | contestant found the optimal answer: 107630884 == 107630884 |
7 | Correct | 6 ms | 760 KB | contestant found the optimal answer: 475357671774 == 475357671774 |
8 | Correct | 4 ms | 888 KB | contestant found the optimal answer: 193556962 == 193556962 |
9 | Correct | 4 ms | 760 KB | contestant found the optimal answer: 482389919803 == 482389919803 |
10 | Correct | 4 ms | 760 KB | contestant found the optimal answer: 490686959791 == 490686959791 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 256 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Integer 0 violates the range [1, 99999] |
2 | Halted | 0 ms | 0 KB | - |