Submission #1170791

#TimeUsernameProblemLanguageResultExecution timeMemory
1170791PieArmySplit the sequence (APIO14_sequence)C++20
100 / 100
638 ms90920 KiB
#include<bits/stdc++.h> typedef long long ll; using namespace std; int n,k; int arr[100023]; ll pref[100023],suf[100023]; int opt[100023][201]; deque<pair<int,ll>>q[201]; void onden_aldiralim_abi(int i,int j){ while(q[j].size()>1){ if(q[j][0].second-pref[q[j][0].first]*suf[i+1]<=q[j][1].second-pref[q[j][1].first]*suf[i+1])q[j].pop_front(); else break; } } void arkalari_toparlayalim_ense_ferahlasin(int j,pair<int,ll>p){ while(q[j].size()>1){ pair<int,ll>a=q[j].back();q[j].pop_back(); pair<int,ll>b=q[j].back(); if(__int128_t(a.second-p.second)*__int128_t(pref[p.first]-pref[b.first])<=__int128_t(b.second-p.second)*__int128_t(pref[p.first]-pref[a.first]))continue; q[j].push_back(a); break; } q[j].push_back(p); } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n>>k; for(int i=1;i<=n;i++){ cin>>arr[i]; pref[i]=pref[i-1]+arr[i]; } for(int i=n;i>=1;i--){ suf[i]=suf[i+1]+arr[i]; } arkalari_toparlayalim_ense_ferahlasin(k,{0,0}); for(int i=1;i<n;i++){ for(int j=1;j<=k;j++){ onden_aldiralim_abi(i,j); if(q[j].size()==0)continue; opt[i][j]=q[j][0].first; arkalari_toparlayalim_ense_ferahlasin(j-1,{i,q[j][0].second+suf[i+1]*(pref[i]-pref[q[j][0].first])}); } } onden_aldiralim_abi(n,0); cout<<q[0][0].second<<endl; int pos=q[0][0].first; vector<int>v; for(int i=1;i<=k;i++){ v.push_back(pos); pos=opt[pos][i]; } while(v.size()){ cout<<v.back()<<" "; v.pop_back(); } }
#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...