제출 #1198471

#제출 시각아이디문제언어결과실행 시간메모리
1198471PlayVoltz수열 (APIO14_sequence)C++20
0 / 100
72 ms163136 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back deque <pair<pii, int> > convexhull; int eval(pii line, int x){ return line.first*x+line.second; } pii query(int x){ while (convexhull.size()>1){ if (eval(convexhull[0].first, x)<eval(convexhull[1].first, x))convexhull.pop_front(); else break; } return mp(eval(convexhull[0].first, x), convexhull[0].second); } long double intersect(pii a, pii b){ return (long double)(b.second-a.second)/(a.first-b.first); } void insert(int m, int c, int id){ pii line = mp(m, c); while (convexhull.size()>1){ int s = convexhull.size(); if (intersect(convexhull[s-1].first, line)<=intersect(convexhull[s-2].first, line))convexhull.pop_back(); else break; } convexhull.push_back(mp(line, id)); } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, k, a; cin>>n>>k; int psum[100005], dp[2][100005], par[205][100005]; for (int i=1; i<=n; ++i)cin>>a, psum[i]=a+psum[i-1]; for (int i=1; i<=n; ++i)dp[1][i] = psum[i]*(psum[n]-psum[i]); for (int l=2; l<=k; ++l){ int j=l%2; convexhull.clear(); for (int i=l; i<=n-k+l; ++i){ insert(psum[i-1], dp[1-j][i-1]-psum[n]*psum[i-1], i-1); pii res = query(psum[i]); dp[j][i] = res.first+psum[n]*psum[i]-psum[i]*psum[i]; par[l][i] = res.second; } } int maxnum=INT_MIN, num; for (int i=1; i<=n; ++i)if (dp[k%2][i]>maxnum)maxnum=dp[k%2][i], num=i; cout<<maxnum<<"\n"; while (num){ cout<<num<<" "; num = par[k][num]; --k; } }
#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...