Submission #541188

#	Time	Username	Problem	Language	Result	Execution time	Memory
541188		Alexandruabcde	Split the sequence (APIO14_sequence)	C++14	11 / 100	68 ms	83116 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair <LL, LL> PLL;
constexpr int NMAX = 1e5 + 5;
constexpr LL INF = 1LL * 1e18;
constexpr int KMAX = 205;
int N, K;

LL dp[NMAX][2];
LL sp[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;

    for (int i = 1; i <= N; ++ i ) {
        int x;
        cin >> x;
        sp[i] = sp[i-1] + 1LL * x;
    }
}

int Q[NMAX];
int bef[NMAX][KMAX];
int vf =0 ;

PLL Slope (int ind, int when) {
    return {sp[ind], dp[ind][((when-1)&1)] - sp[ind] * sp[N]};
}

double Intersect (PLL a, PLL b) {
    double numar = (1.0 * a.second - 1.0 * b.second);
    double numi = (1.0 * b.first - 1.0 * a.first);

    return (numar/numi);
}

void CautBinar (LL coord, int ind, int what) {
    int st = 1, dr = vf;
    int ans = 1;

    while (st <= dr) {
        int mij = (st + dr) / 2;

        pair <double, double> interval;

        if (mij == 1) interval.first = -INF;
        else interval.first = Intersect(Slope(Q[mij-1], what), Slope(Q[mij], what));
        if (mij == vf) interval.second = INF;
        else interval.second = Intersect(Slope(Q[mij], what), Slope(Q[mij+1], what));

        if (interval.second < coord) st = mij + 1;
        else if (interval.first > coord) dr = mij - 1;
        else {
            ans = mij;
            break;
        }
    }

    PLL slope = Slope(Q[ans], what);

    dp[ind][(what&1)] = sp[ind] * (sp[N] - sp[ind]) + slope.first * coord + slope.second;
    bef[ind][what] = Q[ans];
}

void Solve () {
    for (int j = 1; j <= K; ++ j ) {
        vf = 1;
        Q[1] = j-1;

        for (int i = j; i <= N; ++ i ) {
            CautBinar(sp[i], i, j);

            while (vf > 1 && Intersect(Slope(Q[vf-1], j), Slope(Q[vf], j)) >= Intersect(Slope(Q[vf], j), Slope(i, j)) )
                -- vf;

            Q[++vf] = i;
        }
    }

    int index = 0;
    LL ans = -1;
    for (int i = K; i < N; ++ i ) {
        LL val = dp[i][(K&1)];

        if (val > ans) {
            ans = val;
            index = i;
        }
    }

    cout << ans << '\n';

    cout << index << " ";
    for (int i = K-1; i >= 1; -- i ) {
        index = bef[index][i+1];
        cout << index << " ";
    }
}

int main () {
    Read();
    Solve();

    return 0;
}

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