Submission #113310

#	Time	Username	Problem	Language	Result	Execution time	Memory
113310		Runtime_error_	수열 (APIO14_sequence)	C++14	39 / 100	327 ms	3736 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e3+9,K=209;
ll n,k,ans,idx;
ll pre[inf],a[inf];
pair<ll,ll> dp[inf][K];
vector<ll> split;

ll sum(ll x,ll y){
    return pre[y]-pre[x];
}

int main(){

    cin>>n>>k;
    for(ll i=1;i<=n;i++)
        cin>>a[i],pre[i]=pre[i-1]+a[i];
    dp[0][1].first=dp[0][1].second=-1e9;
    for(ll j=1;j<=k;j++)
        for(ll i=1;i<=n;i++)
            for(ll z=0;z<i;z++)
                dp[i][j]=max(dp[i][j],make_pair(dp[z][j-1].first+sum(z,i)*sum(i,n),z));

    for(ll i=1;i<=n;i++)
        if(ans<dp[i][k].first)
            ans=dp[i][k].first,idx=i;

    split.push_back(idx);
    for(ll j=k;j>1;j--)
        idx=dp[idx][j].second,split.push_back(idx);
    reverse(split.begin(),split.end());
    assert(split.size()==k);
    cout<<ans<<endl;
    for(auto o:split)
        cout<<o<<" ";
    cout<<endl;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp: In function 'int main()':
sequence.cpp:33:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(split.size()==k);
            ~~~~~~~~~~~~^~~

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