Submission #973003

#	Time	Username	Problem	Language	Result	Execution time	Memory
973003		oviyan_gandhi	Split the sequence (APIO14_sequence)	C++17	50 / 100	2066 ms	81668 KiB

sequence

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

#define N 100001
#define K 201
int ps[N];
pair<int, int> dp[N][K];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> ps[i];
        ps[i] += ps[i-1];
    }
    for (int l = 1; l <= k; l++)
        for (int i = 1; i <= n; i++)
            for (int j = i-1; j > 0; j--)
                dp[i][l] = max(dp[i][l], {dp[j][l-1].first + ps[j]*(ps[i] - ps[j]), j});
    cout << dp[n][k].first << '\n';
    int curr = n;
    for (int i = k; i > 0; i--){
        cout << dp[curr][i].second << ' ';
        curr = dp[curr][i].second;
    }
    cout << '\n';
    return 0;
}

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