Submission #41656

#	Time	Username	Problem	Language	Result	Execution time	Memory
41656		TAMREF	Split the sequence (APIO14_sequence)	C++11	0 / 100	101 ms	82820 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;

const int mx = 100005;

struct CHT{
    ll A[mx], B[mx];
    int I[mx];
    int p, sz;
    pli query(ll x){
        while(p + 1 < sz && (A[p+1] - A[p]) * x <= B[p] - B[p+1]) ++p;
        return {A[p] * x + B[p], I[p]};
    }
    void insert(ll a, ll b, int i){
        //printf("----inserting y = %lld x + %lld, idx = %d----\n",a,b,i);
        A[sz] = a;
        B[sz] = b;
        I[sz] = i;
        while(p + 1 < sz && (B[sz-2] - B[sz]) * (A[sz] - A[sz-1]) <= (A[sz] - A[sz-2]) * (B[sz-1] - B[sz])){
            //printf("removing y = %lld x + %lld\n",A[sz-1],B[sz-1]);
            A[sz-1] = A[sz];
            B[sz-1] = B[sz];
            I[sz-1] = I[sz];
            --sz;
        }
        ++sz;
    }
    void clear(){
        sz = p = 0;
    }
} C;

int a[mx], S[mx];
int n, k;
ll D[mx][2];
int bck[mx][205];

void input(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> S[i];
        S[i] += S[i-1];
    }
}

void fucking_cht(){
    for(int i = 1; i <= n; i++) D[i][0] = 1e9;
    for(int l = 1, w = 1; l <= k + 1; l++, w ^= 1){
        //printf("lev = %d\n",l);
        C.clear();
        C.insert(0,0,0);
        for(int i = l-1; i <= n; i++){
            if(i >= l){
                tie(D[i][w],bck[i][l]) = C.query(S[i]);
                D[i][w] += (ll)S[i] * S[i];
                //printf("D[%d][%d] = %lld\n",i,l,D[i][w]);
            }
            C.insert(-2LL * S[i], D[i][!w] + (ll)S[i] * S[i], i);
        }
    }

    cout << ((ll)S[n] * S[n] - D[n][(k+1)&1])/2 << '\n';

    stack<int> trace;
    for(int i = k+1, now = n; i >= 1; i--){
        trace.push(bck[now][i]);
        now = bck[now][i];
    }
    trace.pop();
    for(int i=0;i<k;i++){
        cout << trace.top() << ' ';
        trace.pop();
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    input();
    fucking_cht();
}

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