Submission #35756

#	Time	Username	Problem	Language	Result	Execution time	Memory
35756		waynetuinfor	Split the sequence (APIO14_sequence)	C++14	100 / 100	1079 ms	85796 KiB

sequence

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

const int maxn = 1e5 + 10, maxk = 200 + 5;
const long long inf = 1e14;
long long dp[2][maxn], s[maxn];
int t[maxk][maxn];

struct line {
    long long a, b;
    int i;
    long long operator()(const long long &x) const { return a * x + b; }
    bool checkfront(const line &rhs, const long long &x) const { return operator()(x) >= rhs(x); }
    long double inter(const line &rhs) const { return 1.0 * (rhs.b - b) / (a - rhs.a); }
    bool checkback(const line &rhs, const line &pivot) { return inter(pivot) <= rhs.inter(pivot); }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        int a; cin >> a;
        s[i] = s[i - 1] + a;
    }
    dp[0][0] = -inf;
    for (int i = 1; i <= n; ++i) dp[0][i] = 0;
    int cur = 1;
    for (int i = 1; i <= k; ++i) {
        // memset(dp[cur], 0, sizeof(dp[cur]));
        fill(dp[cur], dp[cur] + maxn, -inf);
        deque<line> dq; dq.push_back({ s[1], -s[1] * s[1], 1 });
        // cout << "dp[" << i << "][" << 1 << "] = " << dp[cur][1] << endl;
        for (int j = 2; j <= n; ++j) {
            while (dq.size() >= 2 && dq[1].checkfront(dq[0], s[j])) dq.pop_front();
            dp[cur][j] = dq.front()(s[j]);
            // cout << "dp[" << i << "][" << j << "] = " << dp[cur][j] << endl;
            t[i][j] = dq.front().i;
            // cout << "t[" << i << "][" << j << "] = " << t[i][j]  << endl;
            line tmp = { s[j], dp[cur ^ 1][j] - s[j] * s[j], j };
            while (dq.size() >= 2 && tmp.checkback(dq[dq.size() - 1], dq[dq.size() - 2])) dq.pop_back();
            // if (dq.size() && dq.back().a == tmp.a && dq.back().b >= tmp.b) continue;
            dq.push_back(tmp);
        }
        cur ^= 1;
    }
    /* int cur = 1; dp[0][0] = -inf;
    for (int i = 1; i <= k; ++i) {
        fill(dp[cur], dp[cur] + maxn, -inf);
        for (int j = 1; j <= n; ++j) {
            for (int p = 1; p < j; ++p) {
                if (dp[cur ^ 1][p] + s[p] * (s[j] - s[p]) > dp[cur][j]) {
                    dp[cur][j] = dp[cur ^ 1][p] + s[p] * (s[j] - s[p]);
                    t[i][j] = p;
                }
            }
        }
        cur ^= 1;
    } */
    cout << dp[cur ^ 1][n] << endl;
    stack<int> ans;
    int now = n;
    for (int i = k; i > 0; --i) {
        ans.push(t[i][now]);
        now = t[i][now];
    }
    while (ans.size()) cout << ans.top() << ' ', ans.pop(); cout << endl;
}

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