Submission #1169533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169533		rayan_bd	Split the sequence (APIO14_sequence)	C++20	22 / 100	2094 ms	85320 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 


#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define fi first
#define se second

const int mxN = 205;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;

ll ar[mxN],pref[mxN]; // i,j,k -> choosing a subarray from i to j and splitting it into k seq

// dp[i][j][k].fi = best answer
// dp[i][j][k].se = optimal splitting point we can get if we split it into in the some lth point

pair<ll,pair<ll,ll>> dp[mxN][mxN][mxN];
bool seen[mxN][mxN][mxN];

ll qry(ll i,ll j){
	return pref[j]-pref[i-1];
}

ll f(ll i,ll j,ll k){
	if(k==0) return 0;
	if(i>=j) return -INF;
	if(seen[i][j][k]) return dp[i][j][k].fi;
	dp[i][j][k].fi=-INF;

	for(ll cut=i;cut<j;++cut){
		for(ll nk=0;nk<k;++nk){
			ll curr=f(i,cut,nk)+f(cut+1,j,k-nk-1)+qry(i,cut)*qry(cut+1,j);
			if(dp[i][j][k].fi<curr){
				dp[i][j][k].fi=curr;
				dp[i][j][k].se={cut,nk};
			}
		}
	}
	seen[i][j][k]=1;
	return dp[i][j][k].fi;
}

// i theke cut, with k
// cut+1 theke j
vector<ll> points;

void dfs(ll i,ll j,ll k){
	if(k==0) return;
	points.pb(dp[i][j][k].se.fi);
	dfs(i,dp[i][j][k].se.fi,dp[i][j][k].se.se);
	dfs(dp[i][j][k].se.fi+1,j,k-dp[i][j][k].se.se-1);
}

void lets_go() {
    ll n,k;cin>>n>>k;
    for(ll i=1;i<=n;++i) cin>>ar[i];
    for(ll i=1;i<=n;++i) pref[i]=pref[i-1]+ar[i];
    show(f(1,n,k));
	dfs(1,n,k);
	for(auto it:points) cout<<it<<" ";
}

int main() {


    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    lets_go();

    return 0;
}

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