Submission #1150399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150399		cnnuy	Split the sequence (APIO14_sequence)	C++20	0 / 100	1 ms	328 KiB

sequence

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define m first
#define n second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=2e5+3;

ll dp[202][N],opt[202][N],pf[N],ans=0;
int n,k,a[N];
vector<int> track;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    For(i,1,n) {
        cin >> a[i];
        pf[i]=pf[i-1]+a[i];
    }
    pair<int,int> cur={0,0};
    For(j,1,k) {
        For(i,j,n-1) {
            For(p,j-1,i-1) {
                if (dp[j-1][p]+(pf[i]-pf[p])*(pf[n]-pf[i])>dp[j][i]) {
                    opt[j][i]=p;
                }
                dp[j][i]=max(dp[j][i],dp[j-1][p]+(pf[i]-pf[p])*(pf[n]-pf[i]));
            }
        }   
        For(i,1,n-1) 
            if (dp[j][i]>ans) {
                ans=dp[j][i];
                cur={j,i};
            }
    }
    cout << ans << endl;
    while(cur.m>0) {
        track.pb(cur.n);
        cur={cur.m-1,opt[cur.m][cur.n]};
    }
    reverse(all(track));

    for(auto el: track) cout << el << " ";
    return 0;
}

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