Submission #866292

#	Time	Username	Problem	Language	Result	Execution time	Memory
866292		Dec0Dedd	Split the sequence (APIO14_sequence)	C++14	100 / 100	294 ms	87268 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

const int N = 1e5+1;
const int K = 201;
const ll INF = 3e18+100;

struct line {
    int m;
    ll c;
    int i;

    ll eval(ll x) {return 1ll*m*x+1ll*c;}
    pii interX(line l) {
        return {(c-l.c), (l.m-m)};
    }
};

bool cmp(pii a, pii b) {
    return 0 <= 1ll*b.first*a.second-1ll*a.first*b.second;
}

ll p[N], dp[2][N];
int par[K][N], n, k, a[N], l=N, r=N;
line dq[3*N];

void fs(int &number) {
    register int c;
  
    number = 0;
    c = getchar();
    for (; (c>47 && c<58); c=getchar()) number = number *10 + c - 48;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    fs(n), fs(k);
    for (int i=1; i<=n; ++i) {
        fs(a[i]);
        p[i]=p[i-1]+a[i];
    }

    for (int j=1; j<=k; ++j) {
        dq[r++]=line{0, 0, 0};
        
        for (int i=1; i<=n; ++i) {
            while (r-l >= 2) {
                line a=dq[r-1], b=dq[r-2];
                if (a.eval(p[i]) <= b.eval(p[i])) --r;
                else break;
            }

            line ln=dq[r-1];
            dp[j&1][i]=ln.eval(p[i]), par[j][i]=ln.i;

            line cr={p[i], dp[(j-1)&1][i]-p[i]*p[i], i};
            while (r-l >= 2) {
                line a=dq[l], b=dq[l+1];
                if (cmp(cr.interX(a), a.interX(b))) ++l;
                else break;
            } dq[--l]=cr;
        } l=N, r=N;
    }

    printf("%lld\n", dp[k&1][n]);

    int i=n, x=k;
    while (x > 0) {
        printf("%d ", par[x][i]);
        i=par[x][i], --x;
    } printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:64:25: warning: narrowing conversion of 'p[i]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   64 |             line cr={p[i], dp[(j-1)&1][i]-p[i]*p[i], 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