Submission #742173

#	Time	Username	Problem	Language	Result	Execution time	Memory
742173		viwlesxq	Split the sequence (APIO14_sequence)	C++17	100 / 100	1481 ms	82124 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
typedef string str;

const int N = 1e5 + 1, K = 201;

int n, k;
ll a[N], pref[N];
vector <ll> dp_old(N), dp_new(N);
int p[N][K], v;

ll get(int l, int r) {
    return (pref[r] - pref[l - 1]) * (pref[n] - pref[r]); 
}

void solve(int l, int r, int opt_l, int opt_r) {
    if (l > r) {
        return;
    }
    int mid = (l + r) >> 1;
    pair <ll, int> best = {-1, -1};
    for (int i = opt_l; i <= min(mid - 1, opt_r); ++i) {
        best = max(best, {dp_old[i] + get(i + 1, mid), i});
    }
    dp_new[mid] = best.first;
    int opt = best.second;
    p[mid][v] = opt;
    solve(l, mid - 1, opt_l, opt);
    solve(mid + 1, r, opt, opt_r);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }
    for (int i = 1; i <= n; ++i) {
        dp_old[i] = get(1, i);
        dp_new[i] = get(1, i);
    }
    for (int i = 2; i <= k; ++i) {
        v = i;
        solve(i, n, 1, n);
        dp_old = dp_new;
    }
    ll ans = -1;
    int j = -1;
    for (int i = 1; i <= n; ++i) {
        if (dp_new[i] > ans) {
            ans = dp_new[i];
            j = i;
        }
    }
    vector <int> arr;
    for (int i = k; i >= 1; --i) {
        arr.push_back(j);
        j = p[j][i];
    }
    reverse(arr.begin(), arr.end());
    cout << ans << '\n';
    for (int i : arr) {
        cout << i << ' ';
    }
}

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