제출 #976723

#제출 시각아이디문제언어결과실행 시간메모리
976723tamir1수열 (APIO14_sequence)C++17
28 / 100
2070 ms130940 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...