Submission #395783

#	Time	Username	Problem	Language	Result	Execution time	Memory
395783		kaplanbar	Split the sequence (APIO14_sequence)	C++14	0 / 100	2075 ms	131076 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);


    int n, k;
    cin >> n >> k;

    vector<ll> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    vector<ll> pre(n);
    for(int i = 0; i < n; i++) {
        pre[i] = v[i];
        if(i) pre[i] += pre[i - 1];
    }

    auto get_sum = [&](int l, int r) -> ll {
        ll ret = pre[r];
        if(l) ret -= pre[l - 1];
        return ret;
    };


    vector<vector<ll>> dp(n, vector<ll>(k + 1, -1e9));

    vector<vector<int>> from(n, vector<int>(k + 1, -1));

    for(int i = 0; i < n; i++) dp[i][0] = 0;

    for(int i = 0; i < n; i++) {
        for(int j = 1; j <= k; j++) {
            int l = 0, r = i - 1;
            for(int c = 0; c < 300; c++) {
                int mid1 = (l + l + r) / 3, mid2 = (l + r + r) / 3;
                ll val1 = dp[mid1][j - 1] + get_sum(0, mid1) * get_sum(mid1 + 1, i);
                ll val2 = dp[mid2][j - 1] + get_sum(0, mid2) * get_sum(mid2 + 1, i);
                if(val1 < val2) l = mid1;
                else r = mid2;
            }
            for(int h = l; h <= r; h++) {

                if(dp[h][j - 1] == -1e9) continue;

                ll val = dp[h][j - 1] + get_sum(0, h) * get_sum(h + 1, i);

                if(val >= dp[i][j]) {
                    from[i][j] = h;
                    dp[i][j] = val;
                }
            }
            // for(int t = i; t >= 1; t--) {
                // dp[i][j] = max(dp[i][j], (dp[t - 1][j - 1] + get_sum(0, t - 1) * get_sum(t, i)));
            // }
        }
    }

    cout << dp[n - 1][k] << "\n";
    
    vector<int> ans;
    int cur = n - 1, curk = k;
    while(curk) {
        cur = from[cur][curk];
        ans.push_back(cur);
        curk--;
    }

    reverse(ans.begin(), ans.end());

    for(int x : ans) cout << x + 1 << " ";

    return 0;
}

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