Submission #92224

#	Time	Username	Problem	Language	Result	Execution time	Memory
92224		Vardanyan	Split the sequence (APIO14_sequence)	C++14	0 / 100	2068 ms	72220 KiB

sequence

#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 prevv[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;
                        prevv[i][kk] = j;
                        if(kk == k && (u>=dp[ps][kk] || ps == 0)){
                            ps = i;
                        }
                    }
            }
        }
    }
    cout<<dp[ps][k]<<endl;
    cout<<ps<<endl;
    int kkk = k;
    int i = ps;
    while(1){
        if(kkk == 1) break;
        i = prevv[i][kkk];
        cout<<i<<endl;
        kkk--;
    }
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29