Submission #693680

#	Time	Username	Problem	Language	Result	Execution time	Memory
693680		MurotY	Split the sequence (APIO14_sequence)	C++14	0 / 100	27 ms	27504 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];
int pos[N];
ll 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];
	
	if (k == 0){
		cout << sum;
		return ;
	}
	auto dp = [&] (auto& dp, int ii, int i, int k, ll sum) -> ll {
		
		vector <int> vc;
		vc.clear();
		if (k <= 0 || i >= n+1) {
		     return 0;
		}
		if (memo[i][k] != -1) return memo[i][k];
		ll cur=0, ans=0;
		for (int j=i;j<=n;j++){
			sum-=a[j], cur+=a[j];
			ll res=dp(dp, j, j+1, k-1, sum);
			if (ans < sum*cur+res){
			     ans=sum*cur+res;
		          pos[ii]=j;
			}
			
		}
		memo[i][k]=ans;
		return ans;
	};
	for (int i=0;i<=n;i++){
		for (int j=0;j<=k;j++) memo[i][j]=-1;
	}
	ll res=dp(dp, 0,1, k, sum);
//	for (int i=1;i<=n;i++) cout << pos[i] <<" ";
	
	cout << res <<"\n";
	int tmp=1, cnt=0;
	while (tmp <= n && cnt < k){
		cout << tmp <<" ";
		tmp=pos[tmp]; cnt++;
	}
	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