#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
typedef long long lint;
typedef pair<lint, int> pi;
struct cht{
int s,e;
lint la[100005],lb[100005];
int label[100005];
void insert(lint p, lint q, int piv){
la[e] = p;
lb[e] = q;
label[e] = piv;
while(s+1<e && (lb[e-1] - lb[e-2]) * (la[e] - la[e-1]) <= (la[e-2] - la[e-1])* (lb[e-1] - lb[e])){
la[e-1] = la[e];
lb[e-1] = lb[e];
label[e-1] = label[e];
e--;
}
e++;
}
pi query(lint x){
while(s+1<e && lb[s+1] - lb[s] >= x * (la[s] - la[s+1])) s++;
return pi(la[s]*x+lb[s],label[s]);
}
void clear(){s = e = 0;}
}convexHull;
int n,k;
lint dp[2][100005],a[100005];
int track[205][100005];
int main(){
int t;
scanf("%d %d",&n,&k);
for (int i=0; i<n; i++) {
scanf("%d",&t);
a[i+1] = a[i] + t;
}
for (int t=0; t<=k; t++) {
convexHull.clear();
for (int i=1; i<=n; i++) {
pi x = convexHull.query(a[i]);
track[t][i] = x.second;
dp[t%2][i] = x.first + a[i] * (a[n] - a[i]);
convexHull.insert(a[i],dp[!(t%2)][i]-a[n]*a[i], i);
}
}
printf("%lld\n",dp[k%2][n]);
vector<int> res;
int pos2 = n;
for(int pos1 = k; pos1; pos1--){
res.push_back(track[pos1][pos2]);
pos2 = track[pos1][pos2];
}
while (!res.empty()) {
printf("%d ",res.back());
res.pop_back();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
85584 KB |
Output is correct - contestant found the optimal answer: 108 == 108 |
2 |
Incorrect |
0 ms |
85584 KB |
Output isn't correct - declared answer doesn't correspond to the split scheme: declared = 965, real = 999 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Halted |
0 ms |
0 KB |
- |