Submission #1113040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113040		adaawf	Split the sequence (APIO14_sequence)	C++17	39 / 100	2074 ms	131072 KiB

sequence

#include <iostream>
#include <assert.h>
using namespace std;
long long int a[100005], c[100005], f[100005][205], g[100005][205];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[i] = c[i - 1] + a[i];
    }
    for (int i = 2; i <= k + 1; i++) {
        for (int j = 2; j <= n; j++) {
            f[j][i] = -1e18;
            for (int l = 2; l <= j; l++) {
                long long int h = (c[j] - c[l - 1]) * c[l - 1] + f[l - 1][i - 1];
                if (f[j][i] < h) {
                    f[j][i] = h;
                    g[j][i] = l;
                }
            }
            assert(g[j][i] >= g[j - 1][i]);
        }
    }
    cout << f[n][k + 1] << '\n';
    int h = n, l = k + 1;
    while (l != 1) {
        cout << g[h][l] - 1 << " ";
        h = g[h][l] - 1;
        l--;
    }
}

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