Submission #976725

#TimeUsernameProblemLanguageResultExecution timeMemory
976725tamir1Split the sequence (APIO14_sequence)C++17
50 / 100
2029 ms130952 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,k,i,j,l,a[100001],dp[201][100001],sum[100001],ans,dp2[201][100001],idx; vector<ll> v; int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> k; for(i=1;i<=n;i++){ cin >> a[i]; sum[i]=sum[i-1]+a[i]; } for(l=1;l<=k;l++){ for(i=l;i<n;i++){ for(j=l-1;j<i;j++){ ll x=dp[l-1][j]+(sum[n]-sum[i])*(sum[i]-sum[j]); if(x>=dp[l][i]){ dp[l][i]=x; dp2[l][i]=j; } } } } for(i=k;i<n;i++){ if(dp[k][i]>=ans){ ans=dp[k][i]; idx=i; } } for(i=k;i>=1;i--){ v.push_back(idx); idx=dp2[i][idx]; } reverse(v.begin(),v.end()); cout << ans << "\n"; for(i=0;i<k;i++) cout << v[i] << " "; }
#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...