Submission #756574

#	Time	Username	Problem	Language	Result	Execution time	Memory
756574		Username4132	Split the sequence (APIO14_sequence)	C++14	100 / 100	601 ms	81952 KiB

sequence

#include<iostream>
#include<deque>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define F first
#define S second

const int MAXN=100010;
const ll INF=20000000000010;
int n, k, arr[MAXN], bck[210][MAXN], ord[MAXN];
ll ans[2][MAXN];
ll sum[MAXN];

bool cw(pll a, pll b, pll c){
    return (b.S - a.S)*(c.F - b.F) <= (c.S - b.S)*(b.F - a.F);
}

void opt(int val){
    int ind=val&1;
    deque<pair<pll, int>> hull;
    ans[ind^1][0]=-INF;
    forn(i, n){
        pll pt = {sum[i+1], ans[ind][i]-((ll)sum[i+1])*sum[i+1]};
        while(hull.size()>1 && cw(hull[hull.size()-2].F, hull.back().F, pt)) hull.pop_back();
        hull.push_back({pt, i});
        if(i==n-1) break;
        while(hull.size()>1){
            pll perp = {hull[0].F.S - hull[1].F.S, hull[1].F.F - hull[0].F.F};
            if(sum[i+2]*perp.S<perp.F) break;
            hull.pop_front();
        }
        ans[ind^1][i+1]=sum[i+2]*hull.front().F.F + hull.front().F.S;
        bck[val+1][i+1]=hull.front().S;
    }
}

int main(){
    scanf("%d %d", &n, &k);
    forn(i, n) scanf("%d", arr+i), sum[i+1]=sum[i]+arr[i];
    forn(i, k) opt(i);
    printf("%lld\n", ans[k&1][n-1]);
    int pos=n-1;
    forn(i, k){
        pos=bck[k-i][pos];
        ord[k-i-1]=pos+1;
    }
    forn(i, k) printf("%d ", ord[i]);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:41:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     forn(i, n) scanf("%d", arr+i), sum[i+1]=sum[i]+arr[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