Submission #107062

#	Time	Username	Problem	Language	Result	Execution time	Memory
107062		figter001	Split the sequence (APIO14_sequence)	C++17	0 / 100	89 ms	1656 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 2e5;

int pre[nax];

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> a(n),c;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++){
		pre[i] = a[i];
		if(i)pre[i] += pre[i-1];
	}
	ll ans = 0;
	vector<int> cur;
	cur.push_back(n);
	for(int i=0;i<k;i++){
		ll mx = 0;
		int id = 0,at = 0,q = 0,b = 0;
		int lf = 0,ri = 0;
		for(int j=0;j<n-1;j++){
			if(q == cur[id] - 1){
				q = 0;
				id++;
			}else{
				ll pf = 0;
				if(j-q-1 >= 0)pf = pre[j-q-1];
				ll points = (pre[j] - pf) * (pre[j-q+cur[id]-1] - pre[j]);
				if(points > mx){
					mx = points;
					at = j;
					b = id;
					lf = cur[id] - q - 1;
					ri = cur[id] - lf;
				}
				q++;
			}
		}
		ans += mx;
		cur.erase(cur.begin() + b);
		cur.insert(cur.begin() + b,lf);
		cur.insert(cur.begin() + b,ri);
		c.push_back(at);
	}
	cout << ans << endl;
	// sort(c.begin(),c.end());
	for(int i : c)
		cout << i+1 << ' ';
	printf("\n");
}

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