Submission #373251

#	Time	Username	Problem	Language	Result	Execution time	Memory
373251		flappybird	Split the sequence (APIO14_sequence)	C++14	71 / 100	2082 ms	83216 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define MAX 101010
lld arr[MAX], dp[MAX], p[MAX], s[MAX], ans[MAX];
int path[MAX][202];
void f(lld ind, lld l, lld r, lld low, lld high){
    if(l>r||low>high) return;
    lld i, mid=(l+r)/2, mini=mid-1;
    dp[mid]=0;
    for(i=max(low, ind-1);i<=min(high, mid-1);i++){
        if(dp[mid]<p[i]+s[i]*(s[mid]-s[i])){
            dp[mid]=p[i]+s[i]*(s[mid]-s[i]);
            mini=i;
        }
    }
    path[mid][ind]=(int)mini;
    f(ind, l, mid-1, low, mini);
    f(ind, mid+1, r, mini, high);
}
int main(void){
    lld N, K;
    scanf("%lld %lld", &N, &K);
    lld i;
    for(i=1;i<=N;i++){
        scanf("%lld", &arr[i]);
        s[i]=arr[i]+s[i-1];
    }
    int j;
    for(i=2;i<=K+1;i++){
        f(i, 1, N, 1, N);
        for(j=1;j<=N;j++){
            p[j]=dp[j];
        }
    }
    printf("%lld\n", dp[N]);
    for(i=K+1;i>=2;i--){
        ans[i]=(lld)path[N][i];
        N=(lld)path[N][i];
    }
    for(i=2;i<=K+1;i++){
        printf("%lld ", ans[i]);
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |     scanf("%lld %lld", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |         scanf("%lld", &arr[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