Submission #1255274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255274		duybinhbeo	Split the sequence (APIO14_sequence)	C++20	50 / 100	97 ms	11632 KiB

sequence

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

int dp[1005][1005];
int a[1005], b[1005];
int trace_[1005][1005];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k; 
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = b[i-1] + a[i];
    }

    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= k+1; ++j) {
            dp[i][j] = LLONG_MIN;
            trace_[i][j] = -1;
        }

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

    for (int j = 2; j <= k+1; ++j) {
        for (int i = j; i <= n; ++i) {
            for (int q = j-1; q < i; ++q) {
                if (dp[q][j-1] == LLONG_MIN) continue;
                int val = dp[q][j-1] + b[q] * (b[i] - b[q]);
                if (val > dp[i][j]) {
                    dp[i][j] = val;
                    trace_[i][j] = q;
                }
            }
        }
    }

    cout << dp[n][k+1] << "\n";

    vector<int> ans;
    int u = n, d = k+1;
    while (d > 1 && trace_[u][d] != -1) {
        ans.push_back(trace_[u][d]);
        u = trace_[u][d];
        --d;
    }
    reverse(ans.begin(), ans.end());
    for (int x : ans) cout << x << " ";
}

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