Submission #566427

#	Time	Username	Problem	Language	Result	Execution time	Memory
566427		MurotY	Split the sequence (APIO14_sequence)	C++14	0 / 100	520 ms	32736 KiB

sequence

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ff first
#define ss second
using namespace std;
const int N=1e4+7, M=1e9+7;
ll a[N], dp[N][206], res[N][206], pref[N];
void solve()
{
	int n, k;
	cin >> n >> k;
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i];
     
	for (int i=0;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			for (int q=1;q<=k;q++){
				if (dp[j][q] <= dp[i][q-1]+(pref[j]-pref[i])*(pref[n]-pref[j])){
				     dp[j][q] = dp[i][q-1]+(pref[j]-pref[i])*(pref[n]-pref[j]);
					res[j][q]=i+1;	
				}
			}
		}
	}
	ll ress=0, mx=0;
	for (int i=1;i<=n;i++){
		if (mx < dp[i][k]) mx=dp[i][k], ress=i;
     }
	ll jv=res[ress][k];
	vector <ll> ans;
	while (k > 0){
		ans.push_back(res[jv][k]);
		jv=res[jv][k];
		k--;
	}
	reverse(ans.begin(), ans.end());
	cout << mx <<"\n";
	for (auto l:ans) cout << l <<" ";
	return ;
}
int main()
{
	ios;
	int t=1;
//	cin >> t;
	while (t--){
	    solve();
	    cout <<"\n";
	}
	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