제출 #155040

#제출 시각아이디문제언어결과실행 시간메모리
155040aer0park수열 (APIO14_sequence)C++14
0 / 100
111 ms131076 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; typedef long long ll; typedef pair<ll,ll> pi; ll cnt,n,k,p[100006],a[100006],dp[100005][204]; int sv[100005][204]; vector<int> anw; double get(ll a,ll b,ll q) { return (double)(p[b]*p[b]-p[a]*p[a]+dp[a][q]-dp[b][q])/(double)(p[b]-p[a]); } ll push(ll x,ll c,ll d) { while(cnt<c-1&&(x>=get(cnt,cnt+1,d))) cnt++; sv[c][d+1]=cnt; return x*p[cnt]-p[cnt]*p[cnt]+dp[cnt][d]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i],p[i]=p[i-1]+a[i]; for(int i=1;i<=k;i++) { cnt=0; for(int j=1;j<=n;j++) dp[j][i]=push(p[j],j,i-1); } cout<<dp[n][k]<<"\n"; ll g=n; for(int i=k;i>=1;i--) { g=sv[g][i]; anw.push_back(g); } reverse(anw.begin(),anw.end()); for(int i=0;i<k;i++) cout<<anw[i]<<" "; 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...