Submission #112114

#	Time	Username	Problem	Language	Result	Execution time	Memory
112114		_demon_	Split the sequence (APIO14_sequence)	C++14	50 / 100	152 ms	3676 KiB

sequence

#include <bits/stdc++.h>
    using namespace std;
    long long n,k;
    long long a[1009];
    long long dp[1009][209];
    long long p[1009][209];
    long long sum[1009];
    int main(){
        cin>>n>>k;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
        for(int i=1;i<=n;i++){
            long long crnt=0;
            for(long long j=i;j>=1;j--){
                crnt+=a[j];
                for(int K=1;K<=k+1;K++){
                    if(dp[i][K]<dp[j-1][K-1]+crnt*(sum[n]-sum[i])){
                        dp[i][K]=dp[j-1][K-1]+crnt*(sum[n]-sum[i]);
                        p[i][K]=j-1;
                    }
                    if(dp[i][K]==dp[j-1][K-1]+crnt*(sum[n]-sum[i])){
                        dp[i][K]=dp[j-1][K-1]+crnt*(sum[n]-sum[i]);
                        p[i][K]=max(p[i][K],j-1);
                    }
                }
            }
        }
        cout<<dp[n][k+1]<<endl;
        vector<int>v;
        int ii=n;int kk=k+1;
        while(kk>1){
            v.push_back(p[ii][kk]);
            ii=p[ii][kk];
            kk--;
        }
        reverse(v.begin(),v.end());
        for(int i=0;i<v.size();i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v.size();i++){
                     ~^~~~~~~~~

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