Submission #634726

#	Time	Username	Problem	Language	Result	Execution time	Memory
634726		Son	Split the sequence (APIO14_sequence)	C++14	100 / 100	1495 ms	81516 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back

int A[100005], n, k;
LL P[100005];
LL dp[3][100005];
int pa[205][100005];

LL sub( int l, int r ){
    if ( l > r ) return 0;
    return P[r] - (l == 0 ? 0 : P[l-1]);
}

void dnc( int k, int l, int r, int optl, int optr ){
    if ( l > r ) return;
    int m = ( l + r ) / 2;
    LL &ans = dp[k&1][m];
    int opt = -1;
    for ( int i = optl; i <= min(m, optr); i++ ){
        LL temp = dp[!(k&1)][i-1] + sub(i,m) * 1LL * sub(m+1,n);
        if (opt == -1 || temp > ans ){
            ans = temp;
            opt = i;
        }
    }
    pa[k][m] = opt-1;
    dnc(k,l,m-1,optl,opt);
    dnc(k,m+1,r,opt,optr);
}

int main(){

    scanf("%d%d",&n,&k);
    for ( int i = 1; i <= n; i++ ){
        scanf("%d",&A[i]);
        P[i] = P[i-1] + A[i];
    }

    for ( int i = 1; i <= n; i++ ) dp[0][i] = LLONG_MIN;
    dp[0][0] = 0;

    for ( int i = 1; i <= k; i++ ){
        for ( int j = 0; j <= n; j++ ) dp[i&1][j] = LLONG_MIN;
        dnc(i, 1, n-1, 1, n-1);
    }

    LL ans = n-1;
    for ( int i = k; i < n; i++ ){
        if ( dp[k&1][i] > dp[k&1][ans] ){
            ans = i;
        }
    }
    printf("%lld\n",dp[k&1][ans]);
    int x = ans;
    vector < int > V;
    for ( int i = k; i >= 1; i-- ){
        V.pb(x);
        x = pa[i][x];
    }

    for ( int i = k-1; i >= 0; i-- ){
        printf("%d",V[i]);
        if ( i == 0 ) printf("\n");
        else printf(" ");
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d",&A[i]);
      |         ~~~~~^~~~~~~~~~~~

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