이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
struct line{
ll m, n, id;
ll getval(ll x){
return m*x+n;
}
long double xinter(const line &tar){
return (long double) (tar.n-n) / (long double) (m-tar.m);
}
};
void solve(){
ll n, k;
cin>>n>>k;
vll tep(n);
for(ll i=0;i<n;i++){
cin>>tep[i];
}
vll a;
vll idx;
for(ll i=0;i<n;i++){
if(tep[i]!=0){
a.pb(tep[i]);
idx.pb(i);
}
}
ll siz=a.size();
if(siz<=k+1){
ll ans=0;
ll pre=0;
for(ll i=0;i<siz;i++){
ans+=a[i]*pre;
pre+=a[i];
}
cout<<ans<<'\n';
ll cnt=0;
for(auto it:idx){
if(it>=n-1) break;
cout<<it+1<<' ';
cnt++;
}
for(ll i=0;i<n && cnt<k;i++){
if(tep[i]==0){
cout<<i+1<<' ';
cnt++;
}
}
cout<<'\n';
return;
}
vector<vll> dp(n+1, vll(k+1));
vector<vll> par(n+1, vll(k+1));
vll pre(siz+1);
for(ll i=0;i<siz;i++){
pre[i+1]=pre[i]+a[i];
}
//for()
for(ll tar=2;tar<=k;tar++){
deque<line> dq;
dq.pb({0, 0, 0});
for(ll i=1;i<=siz;i++){
while(dq.size()>=2 && dq[0].getval(pre[i])<dq[1].getval(pre[i])){
dq.pop_front();
}
dp[i][tar]=dq[0].getval(pre[i]);
par[i][tar]=dq[0].id;
line nline={pre[i], dp[i][tar-1]-pre[i]*pre[i], i};
while(dq.size()>=2 && dq[(int) dq.size()-1].xinter(nline)<
dq[(int) dq.size()-2].xinter(nline)){
dq.pop_back();
}
dq.pb(nline);
}
}
for(ll i=1;i<=siz;i++){
dp[i][k]=dp[i][k]+(pre[siz]-pre[i])*pre[i];
}
ll ans=0;
ll cur=1;
for(ll i=1;i<=siz;i++){
if(dp[i][k]>ans){
ans=dp[i][k];
cur=i;
}
}
cout<<ans<<'\n';
vll ans1;
for(ll i=k;i>=1;i--){
//assert(cur-1<-100);
ans1.pb(idx[cur-1]+1);
//cout<<cur<<' ';
cur=par[cur][i];
}
reverse(ans1.begin(), ans1.end());
for(auto it:ans1){
cout<<it<<' ';
}
cout<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
/*
dp[k][i]=max j<i dp[k-1][j]+(pre[i]-pre[j])*pre[j]
=pre[j]*pre[i]+(dp[k-1][j]-pre[j]*pre[j])
*/
# | 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... |