Submission #541197

#	Time	Username	Problem	Language	Result	Execution time	Memory
541197		Alexandruabcde	Split the sequence (APIO14_sequence)	C++14	100 / 100	825 ms	84148 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
constexpr int NMAX = 1e5 + 5;
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 = 1; 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, aux) >= 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;
        }
    }

    cout << dp[N][((K+1)&1)] << '\n';
    int ind = N;
    for (int k = K + 1; k > 1; -- k ) {
        ind = bef[ind][k];

        cout << ind << " ";
    }
}

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

    return 0;
}

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