제출 #1150399

#제출 시각아이디문제언어결과실행 시간메모리
1150399cnnuySplit the sequence (APIO14_sequence)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> #define ll long long #define ldb long double #define endl '\n' #define For(i,l,r) for(int i=l;i<=r;i++) #define ForD(i,r,l) for(int i=r;i>=l;i--) #define m first #define n second #define pb push_back #define all(x) x.begin(),x.end() #define sz(x) (signed)x.size() #define unq(x) x.resize(unique(all(x))-x.begin()) #define F "TASK" #define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout); #ifdef NCGM #include"debug.h" #else #define debug(...) "fr"; #endif using namespace std; const int N=2e5+3; ll dp[202][N],opt[202][N],pf[N],ans=0; int n,k,a[N]; vector<int> track; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k; For(i,1,n) { cin >> a[i]; pf[i]=pf[i-1]+a[i]; } pair<int,int> cur={0,0}; For(j,1,k) { For(i,j,n-1) { For(p,j-1,i-1) { if (dp[j-1][p]+(pf[i]-pf[p])*(pf[n]-pf[i])>dp[j][i]) { opt[j][i]=p; } dp[j][i]=max(dp[j][i],dp[j-1][p]+(pf[i]-pf[p])*(pf[n]-pf[i])); } } For(i,1,n-1) if (dp[j][i]>ans) { ans=dp[j][i]; cur={j,i}; } } cout << ans << endl; while(cur.m>0) { track.pb(cur.n); cur={cur.m-1,opt[cur.m][cur.n]}; } reverse(all(track)); for(auto el: track) cout << el << " "; 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...