Submission #1194206

#TimeUsernameProblemLanguageResultExecution timeMemory
1194206ezzzaySplit the sequence (APIO14_sequence)C++20
50 / 100
2092 ms31964 KiB
#include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back #define int long long const int N=1e5+2; pair<int,int> dp[N][201]; int ps[N]; int a[N]; int par[N]; signed main(){ int n,k; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; ps[i]=ps[i-1]+a[i]; } dp[0][0]={0,0}; for(int i=1;i<=n;i++){ for(int p=1;p<=k;p++){ for(int j=0;j<i;j++){ dp[i][p]=max(dp[i][p], {dp[j][p-1].ff+ (ps[j]* (ps[i]-ps[j])), j}); } } } cout<<dp[n][k].ff<<endl; int x=n; vector<int>ans; while(x!=0){ ans.pb(x); x=dp[x][k].ss; k--; } reverse(ans.begin(),ans.end()); ans.pop_back(); for(auto a:ans)cout<<a<<' '; }
#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...