| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 57009 | Plurm | 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 <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define bad(x,y,z) ((C[y]-C[x])*(M[x]-M[z]) >= (C[z]-C[x])*(M[x]-M[y]))
using namespace std;
int a[100005];
long long dp[100005][2]; // End with i, having j parts;
long long qs[100005];
int par[100005][256];
vector<int> M;
vector<long long> C;
vector<int> idx;
int ptr;
inline int fastscan(){
int x = 0;
int c = getchar();
while(c < 48 || c >= 58) c = getchar();
while(c >= 48 && c < 58){
x *= 10;
x += c-48;
c = getchar();
}
return x;
}
int main(){
int n,k;
n = fastscan();
k = fastscan();
k++;
add(0,0,0);
for(int i = 1; i <= n; i++){
a[i] = fastscan();
qs[i] = qs[i-1] + (long long)a[i];
dp[i][0] = -1e16;
}
for(int j = 1; j <= k; j++){
if(j > 1) add(j-1,qs[j-1], dp[j-1][(j+1) % 2] - qs[j-1]*qs[j-1]);
for(int i = j; i <= n; i++){
if(ptr >= M.size()) ptr = M.size()-1;
while(ptr < M.size()-1 && M[ptr+1]*x + C[ptr+1] > M[ptr]*x + C[ptr]) ptr++;
int id = ptr;
par[i][j] = idx[id];
dp[i][j % 2] = M[id]*qs[i] + C[id];
M.push_back(qs[i]);
C.push_back(dp[i][(j+1) % 2] - qs[i]*qs[i]);
idx.push_back(i);
while(M.size() >= 3 && bad(M.size()-3, M.size()-2, M.size()-1)){
M.erase(M.end()-2);
C.erase(C.end()-2);
idx.erase(idx.end()-2);
}
}
M.clear();
C.clear();
idx.clear();
ptr = 0;
}
printf("%lld\n",dp[n][k % 2]);
int x = n;
stack<int> stk;
for(int j = k; j > 1; j--){
x = par[x][j];
stk.push(x);
}
while(!stk.empty()){
printf("%d ",stk.top());
stk.pop();
}
}