| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 91936 | Vardanyan | Split the sequence (APIO14_sequence) | C++14 | 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;
const long long N = 1000*100+5;
const long long INF = 1000000000000000000;
struct line{
long long k,b;
line():k(0),b(0){}
line(long long _k,long long _b):k(_k),b(_b){}
};
struct node{
node* l;
node* r;
line ln;
node():l(NULL),r(NULL){}
};
long long f(line a, long long x) {
if(a.k == 0 && a.b == 0) return INF;
return (a.k*x+a.b);
}
const long long maxn = 1000000000;
long long n;
void add_line(line nw, node* v, long long l = 0, long long r = maxn) {
long long m = (l + r) / 2;
bool lef = f(nw, l) < f(v->ln, l);
bool mid = f(nw, m) < f(v->ln, m);
if(mid) {
swap(v->ln, nw);
}
if(r - l == 1) return;
else if(lef != mid) {
if(v->l == NULL) v->l = new node();
add_line(nw, v->l, l, m);
} else {
if(v->r == NULL) v->r = new node();
add_line(nw, v->r, m, r);
}
}
long long get(long long x, node* v, long long l = 0, long long r = maxn) {
long long m = (l + r) / 2;
if(r - l == 1) {
if(v == NULL) v = new node();
return f(v->ln, x);
}
else if(x < m) {
if(v->l == NULL) v->l = new node();
return min(f(v->ln, x), get(x, v->l, l, m));
}
else {
if(v->r == NULL) v->r = new node();
return min(f(v->ln, x), get(x, v->r, m, r));
}
}
long long dp[N][205];
int a[N];
int pref[N];
int get(int l,int r){
return pref[r]-pref[l-1];
}
int prev[N][205];
int main()
{
ios_base::sync_with_stdio(false);
int n,k;
cin>>n>>k;
for(int i = 1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
int ps = 0;
for(int kk = 1;kk<=k;kk++){
for(int i = 1;i<=n;i++){
for(int j = kk-1;j<i;j++){
int u = dp[j][kk-1]+get(j+1,i)*get(i+1,n);
if(u>dp[i][kk]){
dp[i][kk] = u;
prev[i][kk] = j;
if(kk == k && u>=dp[ps][kk]){
ps = i;
}
}
}
}
}
cout<<dp[ps][k]<<endl;
cout<<ps<<endl;
int kkk = k;
int i = n;
while(1){
int x = prev[i][kkk];
if(x == 0) break;
cout<<x<<endl;
x = prev[x][kkk-1];
kkk--;
}
return 0;
}