Submission #1113039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113039		adaawf	Split the sequence (APIO14_sequence)	C++17	28 / 100	2079 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];
        g[i][1] = 0;
    }
    for (int i = 2; i <= k + 1; i++) {
        for (int j = 1; j <= n; j++) {
            for (int l = 1; 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;
                }
            }
        }
    }
    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: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29