Submission #746549

#	Time	Username	Problem	Language	Result	Execution time	Memory
746549		cscandkswon	Split the sequence (APIO14_sequence)	C++17	100 / 100	1328 ms	83240 KiB

sequence

#include <cstdio>
#include <algorithm>
using namespace std;

int N, K, v, w;
int A[100005];
long long S[100005];

long long D[100005][2];
int O[100005][205];

void dnc(int l, int r, int x, int y, int k) {
    if (l > r) return;
    int m = (l + r) >> 1;
    int i, p;
    long long q = 0;
    for (i = max(k - 1, x); i <= min(y, m - 1); i++) {
        if (q < (S[m] - S[i]) * (S[N] - S[m]) + D[i][w]) {
            q = (S[m] - S[i]) * (S[N] - S[m]) + D[i][w];
            p = i;
        }
    }
    D[m][v] = q;
    O[m][k] = p;
    if (l == r) return;
    dnc(l, m - 1, x, p, k);
    dnc(m + 1, r, p, y, k);
}

void backtrack(int x, int k) {
    if (k == 0) return;
    backtrack(O[x][k], k - 1);
    printf("%d ", x);
}

int main() {
    int i, j, c = 0;
    scanf("%d %d", &N, &K);
    for (i = 1; i <= N; i++) scanf("%d", A + i);
    for (i = 1; i <= N; i++) S[i] = S[i - 1] + A[i];
    for (i = 1; i <= N; i++) {
        D[i][0] = (S[i]) * (S[N] - S[i]);
        O[i][1]=i;
    }
    v = 1, w = 0;   // write on v, read on w
    for (i = 2; i <= K; i++) {
        for (j = 1; j <= N; j++) D[i][v] = 0;
        dnc(i, N - 1, 1, N - 1, i);
        swap(v, w);
    }
    int a = 0;
    for (i = K; i < N; i++) {
        if (D[i][w] >= D[a][w]) a = i;
    }
    printf("%lld\n", D[a][w]);
    backtrack(a, K);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:15: warning: unused variable 'c' [-Wunused-variable]
   37 |     int i, j, c = 0;
      |               ^
sequence.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:39:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     for (i = 1; i <= N; i++) scanf("%d", A + i);
      |                              ~~~~~^~~~~~~~~~~~~
sequence.cpp: In function 'void dnc(int, int, int, int, int)':
sequence.cpp:26:8: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |     dnc(l, m - 1, x, p, k);
      |     ~~~^~~~~~~~~~~~~~~~~~~

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