Submission #92398

#	Time	Username	Problem	Language	Result	Execution time	Memory
92398		Vardanyan	Split the sequence (APIO14_sequence)	C++14	49 / 100	2072 ms	32856 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];
pair<long long,int> dp[208][N];
int par[208][N];
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];
 //   node* old = new node();
   // node* nold = new node();
    for(int kk = 1;kk<=k;kk++){
        for(int i = kk+1;i<=n;i++){
                int pos = dp[kk-1][i].second;
        a1:

                bool f = false;
                for(int j = pos;j<min(i,pos+100);j++){
                    if(dp[kk-1][j].first+(pref[i]-pref[j])*pref[j]>dp[kk][i].first){
                        dp[kk][i].first = dp[kk-1][j].first+(pref[i]-pref[j])*pref[j];
                        dp[kk][i].second = j;
                        pos = j+1;
                        f = true;
                        break;
                    }
                }
                if(f) goto a1;
        }
    }
    printf("%lld\n",dp[k][n].first);
    int kk = k;
    int nn = n;
    while(kk>0){
        printf("%d\n",dp[kk][nn].second);
        nn = dp[kk][nn].second;
        kk--;
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:15: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:16: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: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29