Submission #92262

#	Time	Username	Problem	Language	Result	Execution time	Memory
92262		Vardanyan	Split the sequence (APIO14_sequence)	C++14	50 / 100	2061 ms	49296 KiB

sequence

#include<bits/stdc++.h>

using namespace std;
int tip;
const int N = 1000*100+5;
const long long INF = 1000000000000000000;
struct line{
    long long k,b;
    int id;
    line():k(0),b(0),id(0){}
    line(long long _k,long long _b,int _id):k(_k),b(_b),id(_id){}
};
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 int maxn = 1000000000;
int n;
void add_line(line nw, node* v, int l = 0, int r = maxn) {
    int 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 == 0) 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+1, r);
    }
}
pair<long long,int> get(int x, node* v, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    if(r - l == 0) {
        if(v == NULL) v = new node();
        return make_pair(f(v->ln, x),v->ln.id);
    }
    else if(x < m) {
        if(v->l == NULL) v->l = new node();
        pair<long long,int> xx = make_pair(f(v->ln,x),v->ln.id);
        pair<long long,int> y = get(x,v->l,l,m);
        return min(xx,y);
    }
    else {
        if(v->r == NULL) v->r = new node();
        pair<long long,int> xx = make_pair(f(v->ln,x),v->ln.id);
        pair<long long,int> y = get(x, v->r, m+1, r);
        return min(xx,y);
    }
}
void clean(node* v){
    if(v->l!=NULL) clean(v->l);
    if(v->r!=NULL) clean(v->r);
    v->ln = line(0,0,0);
}
void havasar(node* x,node* y){
    x->ln = y->ln;
    if(y->l!=NULL){
        if(x->l == NULL) x->l = new node();
        havasar(x->l,y->l);
    }
    if(y->r!=NULL){
        if(x->r == NULL) x->r = new node();
        havasar(x->r,y->r);
    }
}
int a[N];
long long pref[N];
//int suf[N];
pair<long long,int> dp[208][N];
int par[208][N];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    for(int i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
//    for(int i = n;i>=1;i--) suf[i] = suf[i+1]+a[i];
    node* old = new node();
    node* nold = new node();
    for(int kk = 1;kk<=k;kk++){
        tip = kk;
        for(int i = kk+1;i<=n;i++){
            if(kk == 1){
                for(int j = dp[kk-1][i].second;j<i;j++){
                    if(dp[kk-1][j].first+(pref[i]-pref[j])*pref[j]>=dp[kk][i].first){
                        dp[kk][i].first = dp[kk-1][j].first+(pref[i]-pref[j])*pref[j];
                        dp[kk][i].second = j;
                    }
                }
                line now = line({pref[i],dp[kk][i].first-pref[i]*pref[i],i});
                add_line(now,nold);
                continue;
            }
            pair<long long,int> u = get(pref[i],old);
            dp[kk][i].first = -u.first;
            dp[kk][i].second = u.second;
            line now = line({pref[i],dp[kk][i].first-pref[i]*pref[i],i});
            add_line(now,nold);
        }
        havasar(old,nold);
        clean(nold);
    }
    printf("%lld\n",dp[k][n].first);
    int kk = k;
    int nn = n;
    while(kk>0){
        printf("%d\n",dp[kk][nn].second);
        nn = dp[kk][nn].second;
        kk--;
    }
    cout<<endl;
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:85:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
                             ~~~~~^~~~~~~~~~~~

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