Submission #1364806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1364806		norrawichzzz	Split the sequence (APIO14_sequence)	C++20	50 / 100	2094 ms	32068 KiB

sequence

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

#define int long long

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,k;
    cin>> n>> k;

    vector<int> a(n+1), p(n+1, 0);
    for (int i=1; i<=n; i++) cin>> a[i], p[i] = p[i-1]+a[i];

    vector<vector<int>> dp(k+1, vector<int>(n+1, 0));
    vector<vector<int>> bt(k+1, vector<int>(n+1));

    for (int par=1; par<=k; par++) {
        for (int i=1; i<n; i++) {
            for (int j=i; j<n; j++) {
                int val = dp[par-1][i-1]+(p[j]-p[i-1])*(p[n]-p[j]);
                if (dp[par][j] <= val) {
                    dp[par][j] = val;
                    bt[par][j] = i-1;
                }
            }
        }
    }

    int ans=0, id=-1;
    for (int i=1; i<n; i++) {
        if (ans <= dp[k][i]) {
            ans = dp[k][i];
            id = i;
        }
    }

    vector<int> pos;
    int cur=k;
    while (cur>0) {
        int idx = bt[cur][id];
        pos.push_back(id);
        id = idx;
        cur--;
    }   
    reverse(pos.begin(), pos.end());

    cout<< ans<< '\n';
    for (auto &x : pos) 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