Submission #561893

#	Time	Username	Problem	Language	Result	Execution time	Memory
561893		Cyanmond	Split the sequence (APIO14_sequence)	C++17	50 / 100	2071 ms	32860 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr i64 inf = 1ll << 60;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)

template <typename T> bool chmax(T &a, const T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    int N, K;
    cin >> N >> K;
    ++K;
    vector<i64> A(N);
    for (auto &e : A) cin >> e;
    vector<i64> R(N + 1);
    REP(i, N) R[i + 1] = R[i] + A[i];
    auto calc_sum = [&R](int l, int r) { return R[r] - R[l]; };

    vector dp(N + 1, vector(K + 1, (i64)-inf));
    dp[0][0] = 0;
    auto db = dp;
    REP(i, N) {
        REP3(j, i + 1, N + 1) {
            REP(k, K) if (chmax(dp[j][k + 1], dp[i][k] + calc_sum(i, j) * calc_sum(j, N))) db[j][k + 1] = i;
        }
    }

    cout << dp[N][K] << endl;
    int now = N;
    vector<int> data;
    REP(i, K - 1) {
        data.push_back(db[now][K - i]);
        now = db[now][K - i];
    }
    reverse(data.begin(), data.end());
    REP(i, K - 1) cout << data[i] << (i == K - 1 ? '\n' : ' ');
}

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