# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
444762 | impri | Split the sequence (APIO14_sequence) | C++14 | 1235 ms | 89712 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;
int n,k;
int arr[100001];
long long psum[100001];
long long dp[100001][2];
int res[100001][202];
struct line{
long long a,b;
double s;
int p;
};
int main(void){
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> k;
k++;
for(int i=1;i<=n;i++)
cin >> arr[i];
for(int i=1;i<=n;i++)
psum[i]=psum[i-1]+arr[i];
for(int i=1;i<n;i++)
dp[i][1]=psum[i]*(psum[n]-psum[i]);
for(int i=2;i<=k;i++){
vector<line>lines;
lines.push_back({-psum[i-1],dp[i-1][(i+1)%2],10e12,i-1});
int cur=0;
for(int j=i;j<=n;j++){
while(1){
if(cur+1==lines.size())break;
if(lines[cur+1].s<(psum[n]-psum[j]))break;
cur++;
}
dp[j][i%2]=lines[cur].a*(psum[n]-psum[j])+lines[cur].b+psum[j]*psum[n]-psum[j]*psum[j];
res[j][i]=lines[cur].p;
line nxt;
nxt.a=-psum[j];
nxt.b=dp[j][(i+1)%2];
nxt.p=j;
bool ok=true;
while(!lines.empty()){
if(lines.back().a==nxt.a){
if(lines.back().b>nxt.b){
ok=false;break;}
else{
lines.pop_back();
}
}
else{
double point=1.0*(lines.back().b-nxt.b)/(nxt.a-lines.back().a);
if(point>lines.back().s)
{
lines.pop_back();
if(cur==lines.size())
cur--;
}
else{
nxt.s=point;
break;
}
}
}
if(ok)
lines.push_back(nxt);
}
}
cout << dp[n][k%2] <<'\n';
int cur=n;
vector<int>r;
for(int i=k;i>1;i--){
r.push_back(res[cur][i]);
cur=res[cur][i];
}
for(int i=k-2;i>=0;i--)
cout << r[i] << ' ';
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |