Submission #541195

#	Time	Username	Problem	Language	Result	Execution time	Memory
541195		Alexandruabcde	Split the sequence (APIO14_sequence)	C++14	62 / 100	781 ms	84560 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
constexpr int NMAX = 1e5 + 5;
constexpr LL INF = 1LL * 1e18;
constexpr int KMAX = 205;

struct Dreapta {
    LL a, b;

    Dreapta (LL a_, LL b_) : a(a_), b(b_) {}

    LL operator() (LL x) {
        return x * a + b;
    }

    friend LD Intersect (const Dreapta &L1, const Dreapta &L2) {
        LD numar = L2.b - L1.b;
        LD numi = L1.a - L2.a;

        return numar / numi;
    }
};

typedef pair <Dreapta, int> PDI;

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 bef[NMAX][KMAX];

void Solve () {
    for (int j = 1; j <= K+1; ++ j ) {
        int now = (j&1), old = (now^1);

        deque <PDI> D;
        for (int i = j; i <= N; ++ i ) {
            Dreapta aux = Dreapta(sp[i-1], dp[i-1][old] - sp[i-1] * sp[N]);

            while (D.size() >= 2 && Intersect(D[D.size()-2].first, D.back().first) >= Intersect(D.back().first, aux))
                D.pop_back();
            D.push_back({aux, i-1});

            while (D.size() >= 2 && D.front().first(sp[i]) <= D[1].first(sp[i]))
                D.pop_front();

            dp[i][now] = D.front().first(sp[i]) + sp[i] * (sp[N] - sp[i]);
            bef[i][j] = D.front().second;
        }
    }

    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: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 29 / 29