# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
333286 | 2020-12-05T08:59:16 Z | blue | 수열 (APIO14_sequence) | C++11 | 1109 ms | 1260 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 <= ((long long)(1e8))/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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 218 ms | 492 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 745 ms | 364 KB | contestant found the optimal answer: 999 == 999 |
3 | Correct | 556 ms | 392 KB | contestant found the optimal answer: 0 == 0 |
4 | Incorrect | 237 ms | 364 KB | contestant didn't find the optimal answer: 1542521 < 1542524 |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 890 ms | 492 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Correct | 210 ms | 492 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Correct | 186 ms | 364 KB | contestant found the optimal answer: 122453454361 == 122453454361 |
4 | Correct | 232 ms | 492 KB | contestant found the optimal answer: 93663683509 == 93663683509 |
5 | Correct | 318 ms | 364 KB | contestant found the optimal answer: 1005304678 == 1005304678 |
6 | Incorrect | 207 ms | 364 KB | contestant didn't find the optimal answer: 933690 < 933702 |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 235 ms | 364 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Correct | 214 ms | 364 KB | contestant found the optimal answer: 311760000 == 311760000 |
3 | Correct | 194 ms | 364 KB | contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 | Correct | 237 ms | 364 KB | contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 | Incorrect | 256 ms | 492 KB | contestant didn't find the optimal answer: 1019625036 < 1019625819 |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1109 ms | 396 KB | contestant found the optimal answer: 21503404 == 21503404 |
2 | Correct | 249 ms | 492 KB | contestant found the optimal answer: 140412195 == 140412195 |
3 | Incorrect | 207 ms | 364 KB | contestant didn't find the optimal answer: 49119728719153 < 49729674225461 |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 252 ms | 492 KB | contestant found the optimal answer: 1818678304 == 1818678304 |
2 | Correct | 295 ms | 364 KB | contestant found the optimal answer: 1326260195 == 1326260195 |
3 | Incorrect | 307 ms | 364 KB | contestant didn't find the optimal answer: 4963158411504382 < 4973126687469639 |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 238 ms | 1152 KB | contestant found the optimal answer: 19795776960 == 19795776960 |
2 | Correct | 231 ms | 1144 KB | contestant found the optimal answer: 19874432173 == 19874432173 |
3 | Incorrect | 386 ms | 1260 KB | contestant didn't find the optimal answer: 497304059415273010 < 497313449256899208 |
4 | Halted | 0 ms | 0 KB | - |