Submission #392488

#	Time	Username	Problem	Language	Result	Execution time	Memory
392488		giorgikob	Split the sequence (APIO14_sequence)	C++14	50 / 100	337 ms	131076 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e5+5, mod = 1e9+7, sq = 500;

int n,cnt;
ll k[N],A[N],b[N],pre[N],q[N];
ll dp[2][N], where[205][N];
int l,r;

ll get(int x,ll i){
    //cout << k[i] << " " << b[i] << endl;
    return k[i]*x + b[i];
}

bool check1(int x,int y,ll i){
    //cout << "----" << endl;
    //cout << x << " " << y << endl;
    return get(pre[n]-pre[i],x) <= get(pre[n]-pre[i],y);
}

bool check2(int x,int y,ll i){
    //xi = (b[x]-b[i])/(k[i]-k[x])
    //xy = (b[x]-b[y])/(k[y]-k[x])
    //xi >= xy
    if(k[y] == k[i]) return (b[i] >= b[y]);
    if(k[y] == k[x]){
        //cout << k[i] << " " << k[x] << " " << k[y] << endl;
        //cout << i << " " << x << endl;
    }
    assert(k[i] != k[x]);// && k[y] != k[x]);
    return (b[x]-b[i])*(k[y]-k[x]) >= (b[x]-b[y])*(k[i]-k[x]);
}


inline void test_case(){

    cin >> n >> cnt;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
        pre[i] = pre[i-1] + A[i];
    }
    pre[n+1] = pre[n];
    //cout << pre[1] << endl;

    for(int j = 1; j <= cnt+1; j++){
        q[1] = 0; l = 1, r = 2;
        k[1] = 0, b[1] = 0;
        for(int i = 1; i <= n+1; i++){

            while(r-l > 1 && check1(l,l+1,i))l++;

            int x = q[l]; assert(x<i);//cout << x << " ";
            where[j][i] = x;
            dp[1][i] = dp[0][x] + (pre[n]-pre[i])*(pre[i]-pre[x]);

            k[r] = -pre[i];
            b[r] = dp[0][i];
            while(r-l > 1 && check2(r-2,r-1,r))r--;
            q[r] = i;
            k[r] = -pre[i];
            b[r] = dp[0][i];
            r++;
        }
        //cout << endl;
        for(int i = 1; i <= n; i++) dp[0][i] = dp[1][i];// cout << dp[0][i] << " ";
        //cout << endl;
    }

    int ind = 0;
    int mx = -1;
    /*for(int i = 1; i <= n; i++){
        if(dp[0][i] > mx){
            mx = dp[0][i];
            ind = i;
        }
    }*/
    ind = n;
    cout << dp[0][ind] << endl;
    int a = cnt+1;
    while(a>1){
        ind = where[a][ind];
        cout << ind << " ";
        a--;
    }
}

 main(){
    ios::sync_with_stdio(0);

    int T = 1;
    //cin >> T;
    while(T--){
        test_case();
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void test_case()':
sequence.cpp:75:9: warning: unused variable 'mx' [-Wunused-variable]
   75 |     int mx = -1;
      |         ^~
sequence.cpp: At global scope:
sequence.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 |  main(){
      |       ^

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