Submission #900477

#	Time	Username	Problem	Language	Result	Execution time	Memory
900477		ByeWorld	Split the sequence (APIO14_sequence)	C++14	100 / 100	1352 ms	87236 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
//#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 1e5+5;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const ll INF = 2e18;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
 
int n, k;
int a[MAXN], pr[MAXN];
ll dp[MAXN][3]; int ba[MAXN][MAXK];

struct Line {
    ll m, c, idx = -1;
    ll gety(ll x){
        return m*x+c;
    }
};
pii getmid(Line nw, Line oth){
    return pii(nw.c-oth.c, oth.m-nw.m);
}
bool cmp(Line x, Line y, Line z){
    // ld back = (z.c-y.c) / (y.m-z.m);
    // ld nw = (z.c-x.c) / (x.m-z.m);
    pii le = getmid(x, y); pii ri = getmid(y, z);
    //if(le.se==0 || ri.se==0) assert(false);
    return 1ll * le.fi * ri.se < 1ll * ri.fi * le.se; // expected nw lebih gede
}
vector <Line> ch;

void ins(Line x){
    while(ch.size()>=2){
        if(ch.back().m == x.m && ch.back().c == x.c ) return;
        if(!cmp(ch[(int)ch.size()-2], ch.back(), x) ){
            ch.pop_back();
        } else break;
    }
    
    ch.pb(x);
}

pii que(int x){
    ll ans = -1; 
    ll ret = -INF;
    // for(int i=0; i<ch.size(); i++){
    //     ll le = ch[i].gety(x);
    //     if(ret < le){
    //         ret = le; ans = ch[i].idx;
    //     }
    // }
    //     return pii(ret, ans);

    if(ch.size() == 0) return pii(0, -1);
    if(ch.size() == 1){
        return pii(ch[0].gety(x), ch[0].idx);
    }
    int l=1, r=(int)ch.size()-1, mid = 0; 
    while(l-1<=r){
        mid = (l+r)/2;
        ll le = -1; 
        if(0<=mid-1 && mid-1<(int)ch.size()){
            le = ch[mid-1].gety(x);
            if(ret < le){
                ret = le; ans = ch[mid-1].idx;
            }
        }
        ll ri = -1;
        if(0<=mid && mid<(int)ch.size()){
            ri = ch[mid].gety(x);
            if(ret < ri){
                ret = ri; ans = ch[mid].idx;
            }
        }
        if(le < ri) l = mid+2; // ke kanan
        else r = mid-2;
    }
   return pii(ret, ans);
}
signed main(){
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i]; pr[i] = pr[i-1]+a[i];
    }
            
    for(int m=1; m<=k; m++){
        ch.clear();
        for(int i=1; i<=n; i++){ 
            //for(int j=1; j<=i-1; j++) dp[i][m%2] = max(dp[i][m%2], (dp[j][(m-1)%2] - pr[j]*pr[j]) + pr[i] * pr[j]);
            pii te = que(pr[i]);
            dp[i][m%2] = te.fi;
            ba[i][m] = te.se;
            //if(te.se > n) assert(false);

            if(i>=m){
                Line line;
                line.idx = i;
                line.m = pr[i]; 
                line.c = dp[i][(m-1)%2] - 1ll * pr[i]*pr[i];
                ins(line);
            }
            //cout << dp[i][m%2] << " \n"[i==n];
        }

        // for 1->n, j<i
        // dp[i][m] = (dp[j][m-1] - pr[j]*pr[j]) + pr[i] * pr[j]
        // y        =              c             +  x    *  m
    }
    cout << dp[n][k%2] << '\n';

    int nw = n;
    for(int m=k; m>=1; m--){
        nw = ba[nw][m];
        //cout << dp[i][m] <<' ' << i << ' ' << m << '\n';
        if(nw==-1){
            cout << "jnc\n"; exit(0);
        }
        cout << nw << ' ';
    } 
    cout << '\n';
}

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