이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=1e5+7;
ll dp[2][maxn];
int where[maxn][205];
ll a[maxn];
int n,k;
double slope(int i,int j)
{
return (double)(dp[0][i]-dp[0][j])/(a[i]-a[j]);
}
void sol(void){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
}
for(int i=0;i<=n;i++){
dp[0][i]=dp[1][i]=0;
}
deque<int>dq;
for(int i=1;i<=k;i++){
dq.push_back(i-1);
for(int j=i;j<=n;j++){
while(dq.size()>1&&a[n]-a[j]<=slope(dq[0],dq[1]))dq.pop_front();
int tmp=dq.front();
where[i][j]=tmp;
dp[1][j]=dp[0][tmp]+1ll*a[j]*(a[n]-a[j])-1ll*a[tmp]*(a[n]-a[j]);
while(dq.size()>1&&slope(dq[dq.size()-2],dq.back())<=slope(dq.back(),j))dq.pop_back();
dq.push_back(j);
}
dq.clear();
for(int j=i;j<=n;j++)dp[0][j]=dp[1][j];
}
int indx=k;
for(int i=k+1;i<=n;i++){
if(dp[0][i]>dp[0][indx])indx=i;
}
vector<int>v;
cout<<dp[0][indx]<<"\n";
for(int i=k;i>=1;i--){
v.push_back(indx);
indx=where[i][indx];
}
reverse(v.begin(),v.end());
for(int x:v)cout<<x<<" ";
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--){
sol();
}
// you should actually read the stuff at the bottom
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |