제출 #486741

#제출 시각아이디문제언어결과실행 시간메모리
486741status_coding수열 (APIO14_sequence)C++14
71 / 100
146 ms131076 KiB
#include <bits/stdc++.h> using namespace std; struct fCall { int nr, st, dr, stOpt, drOpt; fCall(int nr, int st, int dr, int stOpt, int drOpt) { this->nr=nr; this->st=st; this->dr=dr; this->stOpt=stOpt; this->drOpt=drOpt; } }; long long n,k; long long s[100005]; long long dp[100005][205]; long long last[100005][205]; vector<fCall> fS; inline void solve(int nr, int st, int dr, int stOpt, int drOpt) { if(st > dr) return; int mij=(st+dr)/2; long long maxi=-1, best=mij; int maxOpt=min(mij, drOpt); for(int j=stOpt; j<=maxOpt; j++) { long long nans = (s[mij]-s[j-1])*s[j-1] + dp[j-1][nr-1]; if(nans >= maxi) { maxi=nans; best=j; } } dp[mij][nr]=maxi; last[mij][nr]=best-1; fS.push_back(fCall(nr, st, mij-1, stOpt, best)); fS.push_back(fCall(nr, mij+1, dr, best, drOpt)); } int main() { cin>>n>>k; for(int i=1;i<=n;i++) { cin>>s[i]; s[i] += s[i-1]; } for(int i=1;i<=k;i++) { fS.clear(); fS.push_back(fCall(i, 1, n, 1, n)); while(!fS.empty()) { auto it=fS.back(); fS.pop_back(); solve(it.nr, it.st, it.dr, it.stOpt, it.drOpt); } } cout<<dp[n][k]<<'\n'; int p=n; int nr=k; vector<int> ans; while(true) { p=last[p][nr]; nr--; if(p <= 0) 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...