Submission #486512

#TimeUsernameProblemLanguageResultExecution timeMemory
486512status_codingSplit the sequence (APIO14_sequence)C++14
49 / 100
97 ms131076 KiB
#include <bits/stdc++.h> using namespace std; long long n,k; long long s[100005]; long long dp[100005][201]; int last[100005][201]; void solve(int nr, int st, int dr, int stOpt, int drOpt) { if(st > dr) return; int mij=(st+dr)/2; long long maxi=0, best=-1; for(int j=stOpt;j<=min(drOpt, mij);j++) { long long nval= (s[mij]-s[j-1])*s[j-1] + dp[j-1][nr-1]; if(nval > maxi) { maxi=nval; best=j; } } dp[mij][nr]=maxi; last[mij][nr]=best-1; solve(nr, st, mij-1, stOpt, best); solve(nr, mij+1, dr, best, drOpt); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) cin>>s[i]; for(int i=1;i<=n;i++) s[i]+=s[i-1]; for(int nr=1;nr<=k;nr++) solve(nr, 1, n, 1, n); cout<<dp[n][k]<<'\n'; int nr=k; int p=n; vector<int> ans; while(true) { p = last[p][nr]; nr--; if(!p) break; ans.push_back(p); } reverse(ans.begin(), ans.end()); for(int it : ans) cout<<it<<' '; 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...