Submission #498440

#	Time	Username	Problem	Language	Result	Execution time	Memory
498440		Ierus	Split the sequence (APIO14_sequence)	C++17	50 / 100	105 ms	3432 KiB

sequence

#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define int long long
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e3+3;
const int MOD = 1e9+7;
const bool I = 1;
int n, k, pref[N], a[N];
int get(int l, int r){
	if(l - 1 < 0) return pref[r];
	return pref[r] - pref[l-1];
}
int dp[N][N];
int par[N][N];
void getfast(int res = -1){
	dp[1][1] = get(1, 1) * get(2, n);
	for(int p = 1; p <= k; ++p){
		for(int i = 1; i < n; ++i){
//			if(i == 1 && p == 1) continue;
			int ans = -1;
			for(int j = 0; j < i; ++j){
				int cur = (dp[p-1][j] + get(j + 1, i) * get(i + 1, n));
				if(ans <= cur){
					ans = cur;
					par[p][i] = j;
				}
			}
			dp[p][i] = ans;
		}
	}
	int pos = -1;
	vector<int> r;
	for(int i = 1; i < n; ++i){
		if(res <= dp[k][i]){
			res = dp[k][i];
			pos = i;
		}
	}
	if(pos != -1){
		for(int p = k; p >= 1; --p){
			r.pb(pos);
			pos = par[p][pos];
		}
	}
	reverse(all(r));
	cout << res << '\n';
	for(auto it : r){
		cout << it << ' ';
	}
}
signed main(){
	cin >> n >> k;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		pref[i] = pref[i-1] + a[i];
	}
	getfast();	
}
/*
	7 3
	4 1 3 4 0 2 3

*/

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