#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef tuple<ll, ll, double, ll> t;
int N, K;
vector<int> psum;
double intersect(t L1, t L2) {
return (get<1>(L2)-get<1>(L1))/(get<0>(L1)-get<0>(L2));
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> K; psum.resize(N);
for (auto &i: psum) cin >> i;
for (int i=1; i<N; i++) psum[i] = psum[i-1] + psum[i];
int prev[K][N];
ll DP[2][N];
t g;
fill(&prev[0][0], &prev[K-1][N], 0);
fill(&DP[0][0], &DP[1][N], 0);
for (int k=0; k<K; k++) {
deque<t> F; F.push_front(t(0, -1e14, -1, -1));
for (int i=k+1; i<N; i++) {
g = t(psum[i-1], DP[(k%2)^1][i-1]-psum[i-1]*psum[i-1], 0, i-1);
if (get<0>(F.back()) == get<0>(g) && get<1>(F.back()) < get<1>(g)) {
F.pop_back();
while (!F.empty()) {
g = t(get<0>(g), get<1>(g), intersect(F.back(), g), get<3>(g));
if (get<2>(F.back()) < get<2>(g)) break;
F.pop_back();
}
F.push_back(g);
}
else if (get<0>(F.back()) != get<0>(g)) {
while (!F.empty()) {
g = t(get<0>(g), get<1>(g), intersect(F.back(), g), get<3>(g));
if (get<2>(F.back()) < get<2>(g)) break;
F.pop_back();
}
F.push_back(g);
}
ll X = psum[i];
while (F.size() > 1 && get<2>(F.at(1)) < X) F.pop_front();
DP[k%2][i] = get<0>(F.front()) * X + get<1>(F.front());
prev[k][i] = get<3>(F.front());
}
}
cout << DP[(K-1)%2][N-1] << '\n';
int temp = N-1, q = K-1;
vector<int> L;
while (q>=0) {
L.push_back(prev[q][temp]+1);
temp = prev[q--][temp];
}
sort(L.begin(), L.end());
for (auto &i: L) cout << i << ' ';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Incorrect |
0 ms |
212 KB |
declared answer doesn't correspond to the split scheme: declared = 30269803776, real = 4500000000 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Incorrect |
0 ms |
212 KB |
declared answer doesn't correspond to the split scheme: declared = 4155427745305, real = 122453454361 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Incorrect |
1 ms |
468 KB |
declared answer doesn't correspond to the split scheme: declared = 266542021581429, real = 1989216017013 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
1 ms |
340 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Incorrect |
4 ms |
1108 KB |
declared answer doesn't correspond to the split scheme: declared = 16195970589416914, real = 17902527208914 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
724 KB |
declared answer doesn't correspond to the split scheme: declared = 10285334592, real = 1695400000 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
3796 KB |
declared answer doesn't correspond to the split scheme: declared = 136715067421, real = 7866048541 |
2 |
Halted |
0 ms |
0 KB |
- |