Submission #693651

#	Time	Username	Problem	Language	Result	Execution time	Memory
693651		MurotY	Split the sequence (APIO14_sequence)	C++14	22 / 100	2080 ms	39104 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 ull unsigned long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz size()
using namespace std;
const ll N=1e6+7, M=1e9+7;

ll a[N];
pair <ll, vector <int>> memo[1005][205];
void solve()
{
	int n, k;
	cin >> n >> k;
	
	ll sum=0;
	for (int i=1;i<=n;i++) cin >> a[i], sum+=a[i];
	
	
	auto dp = [&] (auto& dp, int i, int k, ll sum) -> pair <ll,vector <int>> {
		
		vector <int> vc;
		if (k <= 0 || i >= n+1) return {0, vc};
		if (memo[i][k].ff != -1) return memo[i][k];
		ll cur=0, ans=0;
		for (int j=i;j<=n;j++){
			sum-=a[j], cur+=a[j];
			pair <ll, vector <int>> res=dp(dp, j+1, k-1, sum);
			if (ans < sum*cur+res.ff){
				vc.clear();
				vc.push_back(j);
				for (auto l:res.ss) vc.push_back(l);
			     ans=sum*cur+res.ff;
			}
			
		}
		memo[i][k]=make_pair(ans, vc);
		return {ans, vc};
	};
	for (int i=0;i<=n;i++){
		for (int j=0;j<=k;j++) memo[i][j].ff=-1;
	}
	pair <ll, vector <int>> res=dp(dp, 1, k, sum);
	cout << res.ff <<"\n";
	for (auto l:res.ss) cout << l <<" ";
	return ;
}
int main(){
	ios;
	int t=1;	
//	cin >> t;
	while (t--){ 
	    solve();
	    cout << "\n";
	}
	return 0;
}

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