Submission #756554

#	Time	Username	Problem	Language	Result	Execution time	Memory
756554		Username4132	Split the sequence (APIO14_sequence)	C++14	11 / 100	18 ms	4824 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<pll> hull;
    ans[ind^1][0]=-INF;
    int cnt=0;
    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], hull.back(), pt)) hull.pop_back();
        hull.push_back(pt);
        if(i==n-1) break;
        while(hull.size()>1){
            pll perp = {hull[0].S - hull[1].S, hull[1].F - hull[0].F};
            if(sum[i+2]*perp.S<perp.F) break;
            hull.pop_front();
            cnt++;
        }
        ans[ind^1][i+1] = sum[i+2]*hull.front().F + hull.front().S;
        bck[val+1][i+1]=cnt;
    }
}

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

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