Submission #1113045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113045		adaawf	Split the sequence (APIO14_sequence)	C++17	100 / 100	1063 ms	84296 KiB

sequence

#include <iostream>
#include <assert.h>
using namespace std;
long long int a[100005], c[100005], f[100005][2];
int g[100005][205];
void trya(int i, int l, int r, int tl, int tr) {
    if (tl > tr) return;
    long long int mid = (tl + tr) / 2, res = -1, h;
    for (int j = l; j <= r; j++) {
        if (j > mid) break;
        long long int k = (c[mid] - c[j - 1]) * c[j - 1] + f[j - 1][0];
        if (res < k) {
            res = k;
            h = j;
        }
    }
    g[mid][i] = h; f[mid][1] = res;
    trya(i, l, h, tl, mid - 1);
    trya(i, h, r, mid + 1, tr);
}
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 = 1; j <= n; j++) {
            f[j][1] = -1e18;
        }
        trya(i, 2, n, i, n);
        for (int j = 1; j <= n; j++) f[j][0] = f[j][1];
    }
    cout << f[n][1] << '\n';
    int h = n, l = k + 1;
    while (l != 1) {
        cout << g[h][l] - 1 << " ";
        h = g[h][l] - 1;
        l--;
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void trya(int, int, int, int, int)':
sequence.cpp:17:15: warning: 'h' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     g[mid][i] = h; f[mid][1] = res;
      |     ~~~~~~~~~~^~~

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