Submission #685226

#	Time	Username	Problem	Language	Result	Execution time	Memory
685226		PoonYaPat	Split the sequence (APIO14_sequence)	C++14	50 / 100	2075 ms	131072 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,k,ans[100001][201];
ll qs[100001],dp[100001][201];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;

    for (int i=1; i<=n; ++i) {
        cin>>qs[i];
        qs[i]+=qs[i-1];
    }

    for (int i=1; i<n; ++i) dp[i][1]=qs[i]*(qs[n]-qs[i]), ans[i][1]=i;

    for (int j=2; j<=k; ++j) {
        for (int i=1; i<n; ++i) {

            for (int l=1; l<i; ++l) {

                if (dp[i][j]<dp[l][j-1]+(qs[i]-qs[l])*(qs[n]-qs[i])) {
                    ans[i][j]=l;
                    dp[i][j]=dp[l][j-1]+(qs[i]-qs[l])*(qs[n]-qs[i]);
                }
            }

        }
    }
/*
    for (int j=1; j<=k+1; ++j) {
        for (int i=1; i<=n; ++i) cout<<dp[i][j]<<" ";
        cout<<"\n";
    } */

    ll mmax=-1,mnode;
    for (int i=1; i<n; ++i) {
        if (mmax<dp[i][k]) {
            mmax=dp[i][k];
            mnode=i;
        }
    }
    cout<<mmax<<"\n";


    vector<int> v;
    while (k) {
        v.push_back(mnode);
        mnode=ans[mnode][k];
        --k;
    }
    reverse(v.begin(),v.end());

    for (auto s : v) cout<<s<<" ";

}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:50:20: warning: 'mnode' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |         v.push_back(mnode);
      |         ~~~~~~~~~~~^~~~~~~

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