| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1198477 | PlayVoltz | Split the sequence (APIO14_sequence) | C++20 | 0 ms | 0 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;
vector<int> psum(100005, 0);
vector<vector<int> > dp(2, vector<int>(100005, 0)), par(205, vector<int>(100005, 0))
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;
}
}