Submission #1151377

#TimeUsernameProblemLanguageResultExecution timeMemory
1151377AlgorithmWarrior수열 (APIO14_sequence)C++20
100 / 100
646 ms83176 KiB
#pragma GCC optimize ("03,unroll-loops") #include <bits/stdc++.h> using namespace std; int const MAX=1e5+5; long long dp[MAX][2]; int ult[MAX][205]; long long sp[MAX]; int n,k; void read(){ cin>>n>>k; ++k; int i; for(i=1;i<=n;++i){ cin>>sp[i]; sp[i]+=sp[i-1]; } } long long aa(int i){ return sp[i]; } long long bb(int i,int dim){ return dp[i][dim]-sp[i]*sp[i]; } double inters(int i,int j,int dim){ return 1.0*(bb(j,dim)-bb(i,dim))/(aa(i)-aa(j)); } void get_dp(){ int i,j; for(j=2;j<=k;++j){ deque<int>deq; deq.push_back(j-1); int nou=(j&1); int vechi=1-nou; for(i=j;i<=n;++i){ while(deq.size()>1 && inters(deq[0],deq[1],vechi)<=1.0*sp[i]) deq.pop_front(); int ind=deq[0]; dp[i][nou]=bb(ind,vechi)+aa(ind)*sp[i]; ult[i][j]=ind; if(sp[deq.back()]==sp[i]){ ind=deq.back(); if(bb(i,vechi)<=bb(ind,vechi)) continue; deq.pop_back(); } while(deq.size()>1 && inters(deq.back(),deq[deq.size()-2],vechi)>=inters(i,deq.back(),vechi)) deq.pop_back(); deq.push_back(i); } } } void write(){ cout<<dp[n][k&1]<<'\n'; stack<int>stv; int i; int ind=n; for(i=k;i>1;--i){ ind=ult[ind][i]; stv.push(ind); } while(!stv.empty()){ cout<<stv.top()<<' '; stv.pop(); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); read(); get_dp(); write(); return 0; }
#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...