#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 203;
const int maxn=1e5+3;
int n,k;
ll p[maxn];
pair<ll,int> dp[N][maxn];
struct line {
long long m, c;
int idx;
long long eval(long long x) { return m * x + c; }
long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;i++){
int x; cin >> x;
p[i] = x + p[i - 1];
}
for(int i = 1;i <= k;i++){
deque<line>dq;
dq.push_front({p[i],dp[i-1][i].first - p[i] * p[i],i});
for(int j = i + 1;j <= n;j++){
while(dq.size() >= 2 and dq.back().eval(p[j]) <= dq[(int)dq.size()-2].eval(p[j])) dq.pop_back();
dp[i][j].first = dq.back().eval(p[j]);
dp[i][j].second = dq.back().idx;
line cur = {p[j],dp[i - 1][j].first - p[j] * p[j],j};
while(dq.size() >= 2 and cur.intersectX(dq[0]) >= dq[0].intersectX(dq[1])) dq.pop_front();
dq.push_front(cur);
}
// cout<<i<<" ---> ";
// for(int j = i + 1;j <= n;j++) cout<<dp[i][j].first<<' ';
// cout<<'\n';
}
cout<<dp[k][n].first<<'\n';
int idx = dp[k][n].second;
for(int i = k-1;i >= 0;i--){
cout<<idx<<' ';
idx = dp[i][idx].second;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Incorrect |
0 ms |
332 KB |
contestant didn't find the optimal answer: 951 < 999 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
contestant didn't find the optimal answer: 1093924 < 1093956 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
332 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
2 ms |
1996 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Incorrect |
1 ms |
332 KB |
contestant didn't find the optimal answer: 136631827923 < 1499437552673 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
contestant didn't find the optimal answer: 21503354 < 21503404 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
844 KB |
contestant didn't find the optimal answer: 1818678300 < 1818678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
6256 KB |
contestant didn't find the optimal answer: 19795776617 < 19795776960 |
2 |
Halted |
0 ms |
0 KB |
- |