#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,mxk=205;
int n,k,aa[mxn];
int par[mxn][mxk];
ll dp[mxn][2],pre[mxn],ans;
deque<int>cht;
bool comp(int x,int y,ll w,bool z){
ll xx=(-pre[x])*w+dp[x][z],yy=(-pre[y])*w+dp[y][z];
return xx>=yy;
}
bool cmp(int x,int y,int w,bool z){
return (dp[w][z]-dp[y][z])*(pre[y]-pre[x])>=(dp[y][z]-dp[x][z])*(pre[w]-pre[y]);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>aa[i];
pre[i]=pre[i-1]+aa[i];
}
for(int i=1;i<=n;i++){
dp[i][1]=pre[i]*(pre[n]-pre[i]);
}
for(int j=2;j<=k;j++){
bool y=j&1;
cht.push_back(j-1);
for(int i=j;i<n;i++){
//ax+b
ll x=pre[n]-pre[i];
while(cht.size()>1 && !comp(cht[0],cht[1],x,y^1))cht.pop_front();
ll a=-pre[cht[0]],b=dp[cht[0]][y^1];
dp[i][y]=a*x+b+pre[i]*x;
par[i][j]=cht[0];
while(cht.size()>1 && !cmp(cht[cht.size()-2],cht.back(),i,y^1))cht.pop_back();
cht.push_back(i);
}//cout<<'\n';
cht.clear();
}
for(int i=1;i<n;i++){
int y=k&1;
if(dp[i][y]>=dp[ans][y])ans=i;
}
cout<<dp[ans][k&1]<<'\n';
vector<int>v;
while(ans!=0){
v.push_back(ans);
ans=par[ans][k];
k--;
}
reverse(v.begin(),v.end());
for(auto i:v){
cout<<i<<" ";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
0 ms |
2392 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Incorrect |
1 ms |
4444 KB |
contestant didn't find the optimal answer: 1542522 < 1542524 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4444 KB |
contestant didn't find the optimal answer: 1092244 < 1093956 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4440 KB |
contestant didn't find the optimal answer: 407161746 < 610590000 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4444 KB |
contestant didn't find the optimal answer: 20166072 < 21503404 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
10588 KB |
contestant didn't find the optimal answer: 1197227808 < 1818678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
38 ms |
83416 KB |
contestant didn't find the optimal answer: 13199711688 < 19795776960 |
2 |
Halted |
0 ms |
0 KB |
- |