제출 #1099687

#제출 시각아이디문제언어결과실행 시간메모리
1099687hengliao수열 (APIO14_sequence)C++14
100 / 100
274 ms88008 KiB
#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; } double xinter(const line &tar){ return ((double) (tar.n-n)) / (m-tar.m); } }; const ll mxN=1e5+5; ll dp[mxN]; ll new_dp[mxN]; int par[mxN][201]; line dq[mxN]; ll fr, bk, timer; bool good[mxN]; ll l[mxN]; ll r[mxN]; void solve(){ memset(dp, 0, sizeof(dp)); memset(par, 0, sizeof(par)); 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){ 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; } 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[0]={0, 0, 0}; memset(good, 0, sizeof(good)); memset(l, -1, sizeof(l)); memset(r, -1, sizeof(r)); good[0]=1; fr=0; bk=0; timer=0; for(ll i=1;i<=siz;i++){ while(fr!=bk && dq[fr].getval(pre[i])<dq[r[fr]].getval(pre[i])){ fr=r[fr]; } new_dp[i]=dq[fr].getval(pre[i]); par[i][tar]=dq[fr].id; line nline={pre[i], dp[i]-pre[i]*pre[i], i}; while(fr!=bk && dq[bk].xinter(nline)< dq[l[bk]].xinter(nline)){ bk=l[bk]; } timer++; r[bk]=timer; l[timer]=bk; dq[timer]=nline; bk=r[bk]; } for(ll i=1;i<=siz;i++){ dp[i]=new_dp[i]; } } for(ll i=1;i<=siz;i++){ dp[i]=dp[i]+(pre[siz]-pre[i])*pre[i]; } ll ans=0; ll cur=1; for(ll i=1;i<=siz-1;i++){ if(dp[i]>ans){ ans=dp[i]; cur=i; } } cout<<ans<<'\n'; vll ans1; for(ll i=k;i>=1;i--){ //assert(cur-1<-100); /*if(cur==0){ cout<<"wrong\n"; break; }*/ 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]) 7 3 4 1 3 4 0 2 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...