Submission #392506

#	Time	Username	Problem	Language	Result	Execution time	Memory
392506		giorgikob	Split the sequence (APIO14_sequence)	C++14	0 / 100	357 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 = 2e5+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){
    return k[i]*x + b[i];
}

bool check1(int x,int y,int i){
    assert(x > 0);
    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
    assert(x > 0);
    if(k[y] == k[i]) return (b[i] >= b[y]);
    assert(k[y] != k[x]);
    assert(k[i] != 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; assert(n <= 1e5 && cnt <= 200);
    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; i++){

            if(i >= j){
                while(r-l > 1 && check1(l,l+1,i))l++;

                int x = q[l]; assert(x<i);
                where[j][i] = x;
                dp[1][i] = dp[0][x] + (pre[n]-pre[i])*(pre[i]-pre[x]);
            }
            assert(r < N);
            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], dp[1][i] = 0;//, 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];
        assert(ind < N);
        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:72:9: warning: unused variable 'mx' [-Wunused-variable]
   72 |     int mx = -1;
      |         ^~
sequence.cpp: At global scope:
sequence.cpp:90:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 |  main(){
      |       ^

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