Submission #112906

#	Time	Username	Problem	Language	Result	Execution time	Memory
112906		Akashi	Split the sequence (APIO14_sequence)	C++14	100 / 100	1388 ms	80888 KiB

sequence

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

int n, K;
int S[100005];
int which[205][100005];
long long DP[2][100005];
long long *Last, *Now;

void divide(int k, int L, int R, int whL, int whR){
    int mid = (L + R) >> 1;

    for(int j = whL; j <= whR && j <= mid ; ++j){
        long long aux = Last[j - 1] + 1LL * (S[mid] - S[j - 1]) * (S[n] - S[mid]);
        if(aux > Now[mid]) Now[mid] = aux, which[k][mid] = j;
    }
    if(L < R){
        divide(k, L, mid - 1, whL, which[k][mid]);
        divide(k, mid + 1, R, which[k][mid], whR);
    }
}

void solve(int n, int k){
    if(k == 1) return ;
    solve(which[k][n] - 1, k - 1);
    printf("%d ", which[k][n] - 1);
}

int main()
{
//    freopen("sequence.in", "r", stdin);
//    freopen("sequence.out", "w", stdout);

    scanf("%d%d", &n, &K);
    for(int i = 1; i <= n ; ++i) scanf("%d", &S[i]), S[i] += S[i - 1];

    for(int i = 1; i <= n ; ++i) DP[1][i] = 1LL * S[i] * (S[n] - S[i]);

    for(int k = 2; k <= K + 1 ; ++k){
        Last = DP[!(k & 1)], Now = DP[k & 1];

        for(int i = 1; i <= n ; ++i) Now[i] = -1, which[k][i] = -1;

        divide(k, k, n, k, n);
    }

    printf("%lld\n", DP[!(K & 1)][n]);

    solve(n, K + 1);

    return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &K);
     ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:35:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%d", &S[i]), S[i] += S[i - 1];
                                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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