Submission #92368

#	Time	Username	Problem	Language	Result	Execution time	Memory
92368		Vardanyan	Split the sequence (APIO14_sequence)	C++14	39 / 100	2060 ms	95068 KiB

sequence

//#pragma GCC optimize "-O3"
#include<bits/stdc++.h>

using namespace std;
const int N = 1000*100+5;
const long long INF = 1000000000000000000;
int tip;
struct line{
    long long k,b;
    int id;
    int tip;
    line():k(0),b(0),id(0),tip(0){}
    line(long long _k,long long _b,int _id):k(_k),b(_b),id(_id){}
};
struct node{
    int l;
    int r;
    line ln;
    node():l(NULL),r(NULL){}
};
int timer[2];
node t[2][10*N];
long long f(line a,  long long x) {
    if((a.k == 0 && a.b == 0) || a.tip == 0) return INF;
    return -(a.k*x+a.b);
}
const int maxn = 1000000000;
void add_line(int num,line nw, int v,int l = 0,int r = maxn){
    int m = (l+r)/2;
    t[num][v].ln.tip = tip;
    bool lef = f(nw,l)<f(t[num][v].ln,l);
    bool mid = f(nw,m)<f(t[num][v].ln,m);
    if(mid){
        swap(t[num][v].ln,nw);
    }
    if(l == r) return;
    if(lef!=mid){
        if(t[num][v].l == 0) t[num][v].l = ++timer[num];
        add_line(num,nw,t[num][v].l,l,m);
    }
    else{
        if(t[num][v].r == 0) t[num][v].r = ++timer[num];
        add_line(num,nw,t[num][v].r,m+1,r);
    }
}
pair<long long,int> get(int num,int x,int v,int l = 0,int r = maxn){
        if(t[num][v].ln.id == 0 || t[num][v].ln.tip == 0) return {INF,0};
        if(l == r) return {f(t[num][v].ln,x),t[num][v].ln.id};
        int m = (l+r)/2;
        if(x<m){
            return min({f(t[num][v].ln,x),t[num][v].ln.id},get(num,x,t[num][v].l,l,m));
        }
        else return min({f(t[num][v].ln,x),t[num][v].ln.id},get(num,x,t[num][v].r,m+1,r));

}
void clean(int num,int v){
    if(t[num][v].l!=0) clean(num,t[num][v].l);
    if(t[num][v].r!=0) clean(num,t[num][v].r);
    t[num][v].ln = line(0,0,0);
}
void havasar(int v0,int v1){
    t[0][v0].ln = t[1][v1].ln;
    if(t[1][v1].l){
        if(t[0][v0].l == 0) t[0][v0].l = ++timer[0];
        havasar(t[0][v0].l,t[1][v1].l);
    }
    if(t[1][v1].r){
        if(t[0][v0].r == 0) t[0][v0].r = ++timer[0];
        havasar(t[0][v0].r,t[1][v1].r);
    }
}
int a[N];
long long pref[N];
pair<long long,int> dp[208][N];
int par[208][N];
int main()
{
    int n,k;
    scanf("%d%d",&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];
 //   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});
                now.tip = tip;
                add_line(1,now,0);
                continue;
            }
            pair<long long,int> u = get(0,pref[i],0);
            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});
            now.tip = tip;
            add_line(1,now,0);
        }
        havasar(0,0);
      //  clean(1,0);
    }
    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--;
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

sequence.cpp: In constructor 'node::node()':
sequence.cpp:19:26: warning: converting to non-pointer type 'int' from NULL [-Wconversion-null]
     node():l(NULL),r(NULL){}
                          ^
sequence.cpp:19:26: warning: converting to non-pointer type 'int' from NULL [-Wconversion-null]
sequence.cpp: In function 'int main()':
sequence.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:80: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: 0 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29