Submission #41664

#	Time	Username	Problem	Language	Result	Execution time	Memory
41664		TAMREF	Split the sequence (APIO14_sequence)	C++11	100 / 100	1364 ms	85444 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll,int> pli;
 
const int mx = 100005;
const ll inf = 2e18;
 
//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){
        A[sz] = a;
        B[sz] = b;
        I[sz] = i;
        while(p+1<sz && (B[sz] - B[sz-2]) * (A[sz-1] - A[sz]) >= (A[sz-2] - A[sz])* (B[sz] - 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(){
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++){
        scanf("%d",&S[i]);
        S[i] += S[i-1];
    }
}
 
void fucking_cht(){
    for(int i = 1; i <= n; i++) D[i][0] = inf;
    for(int l = 1, w = 1; l <= k + 1; l++, w ^= 1){
        //printf("\n#####lev = %d#####\n",l);
        clear();
        insert(0,0,0);
        for(int i = l-1; i <= n; i++){
            if(i >= l){
                pli p = query(S[i]);
                D[i][w] = p.first + (ll)S[i] * S[i];
                bck[i][l] = p.second;
                //printf("S[%d] = %d, D[%d][%d] = %lld, bck[%d][%d] = %d\n",i,S[i],i,l,D[i][w],i,l,bck[i][l]);
            }
            if(D[i][!w] != inf) insert(-2LL * S[i], D[i][!w] + (ll)S[i] * S[i], i);
        }
    }
 
    printf("%lld\n",((ll)S[n] * S[n] - D[n][(k+1)&1])/2);
 
    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++){
        printf("%d ",trace.top());
        trace.pop();
    }
}
 
int main(){
    input();
    fucking_cht();
}

Compilation message (stderr)

sequence.cpp: In function 'void input()':
sequence.cpp:41:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
                        ^
sequence.cpp:43:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&S[i]);
                          ^

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