Submission #92432

#	Time	Username	Problem	Language	Result	Execution time	Memory
92432		Vardanyan	Split the sequence (APIO14_sequence)	C++14	100 / 100	1281 ms	81456 KiB

sequence

//#pragma GCC optimize "-O3"
#include<bits/stdc++.h>

using namespace std;
const int N = 1000*100+5;
const long long INF = 1000000000000000000;

int a[N];
long long pref[N];
long long dp[2][N];
int par[202][N];
void get(int kk,int l,int r,int s,int e){
    if(l>r) return;
    int i = (l+r)/2;
    int pos = -1;
    long long mx = -1;
    for(int j = s;j<=e;j++){
            if(dp[0][j]+(pref[i]-pref[j])*pref[j]>mx){
                       pos = j;
                       mx = dp[0][j]+(pref[i]-pref[j])*pref[j];
                       dp[1][i] = dp[0][pos]+(pref[i]-pref[pos])*pref[pos];
                       par[kk][i] = pos;
            }
    }
   // pos = max(1,pos);
    get(kk,l,i-1,s,pos);
    get(kk,i+1,r,pos,e);
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    for(int i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
    for(int kk = 1;kk<=k;kk++){
            get(kk,kk,n,kk,n);
            for(int i = 0;i<=n;i++) dp[0][i] = dp[1][i];
            for(int i = 0;i<=n;i++) dp[1][i] = 0;
    }

    printf("%lld\n",dp[0][n]);
    int kk = k;
    int nn = n;
    while(kk>0){
        printf("%d\n",par[kk][nn]);
        nn = par[kk][nn];
        kk--;
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:32: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:33:34: 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",&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