Submission #1200545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200545		PlayVoltz	Split the sequence (APIO14_sequence)	C++20	100 / 100	1744 ms	82700 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;            // 64-bit only when it matters

using pii = pair<i64,i64>;        // slopes / intercepts still 64-bit
using Line = pair<pii,int>;       // (m,c) , id   – id fits in 32 bits

deque<Line> hull;

i64 eval(const pii &ln, i64 x) { return ln.first * x + ln.second; }

pair<i64,int> query(i64 x) {
    while (hull.size() > 1 &&
           eval(hull[0].first, x) < eval(hull[1].first, x))
        hull.pop_front();
    return { eval(hull[0].first, x) , hull[0].second };
}

long double inter(const pii &a, const pii &b) {
    return static_cast<long double>(b.second - a.second) /
           static_cast<long double>(a.first - b.first);
}

void insert(i64 m, i64 c, int id) {
    pii ln{m,c};
    while (hull.size() > 1) {
        int s = (int)hull.size();
        if (inter(hull[s-1].first, ln) <= inter(hull[s-2].first, ln))
            hull.pop_back();
        else break;
    }
    hull.push_back({ln, id});
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;         cin >> n >> k;
    vector<i64> psum(n+1, 0);
    vector<vector<i64>> dp(2, vector<i64>(n+1, 0));

    /* parent ⟶ 32-bit is enough: it only stores indices ≤ n */
    vector<vector<int>> par(k+1, vector<int>(n+1, 0));

    for (int i = 1, a; i <= n; ++i) {
        cin >> a;
        psum[i] = psum[i-1] + a;
    }

    for (int i = 1; i <= n; ++i)
        dp[1][i] = psum[i] * (psum[n] - psum[i]);   // base layer

    for (int l = 2; l <= k; ++l) {
        int cur = l & 1, prv = cur ^ 1;
        hull.clear();

        for (int i = l; i <= n - k + l; ++i) {
            insert(psum[i-1],
                   dp[prv][i-1] - psum[n] * psum[i-1],
                   i-1);

            auto [best, id] = query(psum[i]);
            dp[cur][i] = best + psum[n] * psum[i] - psum[i] * psum[i];
            par[l][i]  = id;                        // parent is only 32-bit
        }
    }

    // find optimum
    i64 best = LLONG_MIN; int idx = -1;
    for (int i = 1; i <= n; ++i)
        if (dp[k & 1][i] > best) { best = dp[k & 1][i]; idx = i; }

    cout << best << '\n';

    /* traceback – parents are still available */
    for (int l = k; l && idx; --l) {
        cout << idx << ' ';
        idx = par[l][idx];
    }
    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