| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 927489 | AlphaMale06 | Split the sequence (APIO14_sequence) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
#define int long long
#define pb push_back
#define F first
#define S second
int dp[2][205][100010];
deque<pair<line, int>> cht;
struct line{
int slope, c;
int eval(int x){
return slope*x+c;
}
ld interx(line & a){
return (ld)(a.c-c)/(ld)(slope-a.slope);
}
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
int a[n];
int pref[n+1];
pref[0]=0;
for(int i=0; i< n; i++){
cin >> a[i];
pref[i+1]=pref[i]+a[i];
}
for(int j=1; j<=k; j++){
cht.pb({{-pref[j-1], dp[0][j-1][j]}, j});
for(int i=j+1; i<=n; i++){
int x = pref[n]-pref[i-1];
while(cht.size()>=2){
pair<line, int> l = cht.back();
cht.pop_back();
if(l.F.eval(x)>cht.back().F.eval(x)){
cht.push_back(l);
break;
}
}
dp[0][j][i]=cht.back().F.eval(x)+pref[i-1]*(pref[n]-pref[i-1]);
dp[1][j][i]=cht.back().S;
pair<line, int> np = {{-pref[i-1], dp[0][j-1][i]}, i};
while(cht.size()>=2){
pair<line, int> f = cht.front();
cht.pop_front();
if(f.F.slope==np.F.slope){
if(f.F.c<=np.F.c)continue;
else break;
}
ld inter1 = f.F.interx(cht.front().F);
ld inter2 = np.F.interx(cht.front().F);
if(inter2<inter1){
cht.push_front(f);
break;
}
}
cht.push_front(np);
}
while(cht.size())cht.pop_back();
}
int ans=0;
int ind=0;
for(int i=1; i<=n; i++){
if(dp[0][k][i]>=ans){
ans=dp[0][k][i];
ind=i;
}
}
cout << ans << '\n';
vector<int> con;
con.pb(ind);
for(int i=k; i>1; i--){
con.pb(dp[1][i][ind]);
ind=dp[1][i][ind];
}
sort(con.begin(), con.end());
for(int i=0; i<k; i++){
cout << con[i]-1 << " ";
}
cout << '\n';
}