Submission #634710

#	Time	Username	Problem	Language	Result	Execution time	Memory
634710		Son	Split the sequence (APIO14_sequence)	C++14	71 / 100	455 ms	131072 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[205][100005];
int pa[205][100005];

LL sub( int l, int r ){
    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][m];
    int opt = -1;
    ans = dp[k-1][m-1] + 1LL * sub(m,m) * sub(m+1,n);
    opt = m;
    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;
    if ( opt == -1 ) assert(1==2);
    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 <= k; i++ ){
        for ( int j = 1; j < n; j++ ) dp[i][j] = 0;
        dnc(i, i, n-1, 1, n-1);
    }

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

    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:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         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: 0 / 29