# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
333285 | 2020-12-05T08:57:34 Z | blue | Split the sequence (APIO14_sequence) | C++11 | 208 ms | 1132 KB |
#include <iostream> #include <vector> using namespace std; int main() { long long n, k; cin >> n >> k; long long a[n+1]; a[0] = 0; for(long long i = 1; i <= n; i++) { cin >> a[i]; a[i] += a[i-1]; } vector<long long> split(k+2); //The i'th split occurs between split[i] and split[i+1] for(long long i = 0; i <= k; i++) split[i] = i; split[k+1] = n; bool flag = 0; long long x, y, m; long long segA, segB; for(int i = 1; i <= (2e7)/(k); i++) { flag = 1; for(long long i = k; i >= 1; i--) { segA = a[split[i]] - a[split[i-1]]; segB = a[split[i+1]] - a[split[i]]; if(segA == segB) { continue; } if(segA > segB) { if(segA - (a[split[i]] - a[split[i]-1]) < segB) { continue; } } if(segB > segA) { if(segB - (a[split[i]+1] - a[split[i]]) < segA) { continue; } } flag = 0; x = split[i-1] + 1; y = split[i+1] - 1; while(y - x > 1) { m = (x+y)/2; segA = a[m] - a[split[i-1]]; segB = a[split[i+1]] - a[m]; if(segA == segB) { x = y = m; } else if(segA > segB) { y = m; if(segA - (a[m] - a[m-1]) < segB) x = m; } else { x = m; if(segA > segB - (a[m+1] - a[m])) y = m; } } if(x == y) split[i] = x; else split[i] = ((a[split[i+1]] - a[y] > a[x] - a[split[i]]) ? y : x); } } long long res = a[n] * a[n]; for(long long i = 1; i <= k+1; i++) res -= (a[split[i]] - a[split[i-1]]) * (a[split[i]] - a[split[i-1]]); cout << res/2 << '\n'; for(long long i = 1; i <= k; i++) cout << split[i] << ' '; cout << '\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 364 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 140 ms | 492 KB | contestant found the optimal answer: 999 == 999 |
3 | Correct | 110 ms | 364 KB | contestant found the optimal answer: 0 == 0 |
4 | Incorrect | 50 ms | 256 KB | contestant didn't find the optimal answer: 1542521 < 1542524 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 174 ms | 492 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Correct | 42 ms | 364 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Correct | 37 ms | 364 KB | contestant found the optimal answer: 122453454361 == 122453454361 |
4 | Correct | 48 ms | 364 KB | contestant found the optimal answer: 93663683509 == 93663683509 |
5 | Correct | 62 ms | 364 KB | contestant found the optimal answer: 1005304678 == 1005304678 |
6 | Incorrect | 57 ms | 492 KB | contestant didn't find the optimal answer: 933690 < 933702 |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 364 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Correct | 41 ms | 384 KB | contestant found the optimal answer: 311760000 == 311760000 |
3 | Correct | 38 ms | 492 KB | contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 | Correct | 47 ms | 364 KB | contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 | Incorrect | 50 ms | 364 KB | contestant didn't find the optimal answer: 1019625036 < 1019625819 |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 208 ms | 492 KB | contestant found the optimal answer: 21503404 == 21503404 |
2 | Correct | 50 ms | 384 KB | contestant found the optimal answer: 140412195 == 140412195 |
3 | Incorrect | 43 ms | 364 KB | contestant didn't find the optimal answer: 49119728719153 < 49729674225461 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 364 KB | contestant found the optimal answer: 1818678304 == 1818678304 |
2 | Correct | 60 ms | 440 KB | contestant found the optimal answer: 1326260195 == 1326260195 |
3 | Incorrect | 79 ms | 364 KB | contestant didn't find the optimal answer: 4963158411504382 < 4973126687469639 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 65 ms | 1132 KB | contestant found the optimal answer: 19795776960 == 19795776960 |
2 | Correct | 60 ms | 1132 KB | contestant found the optimal answer: 19874432173 == 19874432173 |
3 | Incorrect | 132 ms | 1132 KB | contestant didn't find the optimal answer: 497304059415273010 < 497313449256899208 |
4 | Halted | 0 ms | 0 KB | - |