Submission #73535

#	Time	Username	Problem	Language	Result	Execution time	Memory
73535		Vardanyan	Split the sequence (APIO14_sequence)	C++98	39 / 100	192 ms	4612 KiB

sequence

//#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const long long N = 2000+7;
long long a[N];
long long pref[N];
//long long suf[N];
pair<long long,long long> check(long long l,long long r){
    long long ans = 0;
    long long pos = l;
    for(long long i = l;i<=r-1;i++){
        long long x = pref[i]-pref[l-1];
        long long y = pref[r]-pref[i];
        x*=y;
        if(x>ans){
            ans = x; pos = i;
        }
    }
    return make_pair(ans,pos);
}
pair<long long,long long> dp[N][N];
long long par[N][N];
int main()
{
    long long n,k;
    scanf("%lld%lld",&n,&k);
    for(long long i = 1;i<=n;i++) scanf("%lld",&a[i]);
    for(long long i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
//    for(long long i = n;i>=1;i--) suf[i] = suf[i+1]+a[i];
    for(long long i = 1;i<=n;i++){
        dp[1][i] = check(1,i);
    }
    for(long long kk = 2;kk<=k;kk++){
        for(long long i = 1;i<=n;i++){
            for(long long j = 1;j<i;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;
                }
            }
        }
    }
    cout<<dp[k][n].first<<endl;
    long long kk = k;
    long long nn = n;
    while(dp[kk][nn].second!=0){
        cout<<dp[kk][nn].second<<" ";
        nn = dp[kk][nn].second;
        kk--;
    }
    cout<<endl;
    return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp:27:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(long long i = 1;i<=n;i++) scanf("%lld",&a[i]);
                                   ~~~~~^~~~~~~~~~~~~~

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