Submission #35755

#	Time	Username	Problem	Language	Result	Execution time	Memory
35755		waynetuinfor	Split the sequence (APIO14_sequence)	C++14	50 / 100	2000 ms	84604 KiB

sequence

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

const int maxn = 1e5 + 10, maxk = 200 + 5;
const long long inf = 1e18;
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 long inter(const line &rhs) const { return (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;
    }
    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] * s[p];
                    t[i][j] = p;
                }
            }
            // cout << "dp[" << i << "][" << j << "] = " << dp[cur][j] << endl;
            // cout << "t[" << i << "][" << j << "] = " << t[i][j] << endl;
        }
        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: 0 / 21
• Subtask 6: 0 / 29