Submission #112096

#	Time	Username	Problem	Language	Result	Execution time	Memory
112096		_demon_	수열 (APIO14_sequence)	C++14	28 / 100	111 ms	3704 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(int 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;
                }
            }
        }
    }
    cout<<dp[n][k+1]<<endl;
    vector<int>v;
    int ii=n;int kk=k+1;
    while(p[ii][kk]!=0){
        v.push_back(p[ii][kk]);
        ii=p[ii][kk];
        kk--;
    }
    if(v.size()!=k)cout<<"wefwefwe"<<endl;
    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:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(v.size()!=k)cout<<"wefwefwe"<<endl;
        ~~~~~~~~^~~
sequence.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++){
                 ~^~~~~~~~~

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