Submission #583081

#	Time	Username	Problem	Language	Result	Execution time	Memory
583081		1ne	Split the sequence (APIO14_sequence)	C++14	0 / 100	1086 ms	3744 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,k;
	cin>>n>>k;
	vector<long long>arr(n);
	for (int i = 0;i<n;++i)cin>>arr[i];
	vector<long long>pref(n + 1,0);
	for (int i = 0;i<n;++i){
		pref[i + 1] = pref[i] + arr[i];
	}
	auto getscore = [&](int l,int r){
		return pref[r] - pref[l];
	};
	set<int>index;
	vector<int>ans(k);
	set<pair<long long,long long>>brr;
	long long score = 0;
	long long answer=0;
	for (int i = 0;i<k;++i){
		brr.insert({arr[i],i});
		ans[i] = i + 1;
		score+=getscore(i,i + 1) * getscore(i + 1,n);
		index.insert(i);
	}
	vector<int>cur = ans;
	answer = score;
	for (int i = k;i<n - 1;++i){
		ans.push_back(i + 1);
		brr.insert({arr[i],i});
		score+=getscore(i,i + 1) * getscore(i + 1,n);
		index.insert(i);
		auto u = *brr.begin();
		if (next(index.find(u.second)) == index.end()){
			u = *next(brr.begin());
		}
		brr.erase(brr.find(u));
		auto it = index.find(u.second);
		bool ok1 = true,ok2 = true;
		if (next(it)==index.end())ok1 = false;
		if (it == index.begin())ok2 = false;
		int nxt = *next(it);
		int p = *prev(it);
		long long score1 = (ok2)?(getscore(u.second + 1,n) * (arr[p] + arr[u.second]) - getscore(p + 1,n) * arr[p] - getscore(u.second + 1,n) * arr[u.second]):0;
		long long score2 = (ok1)?(getscore(nxt + 1,n) * (arr[nxt] + arr[u.second]) - getscore(nxt + 1,n) * arr[nxt] - getscore(u.second + 1,n) * arr[u.second]):0;
		if ((ok1 && score2 > score1)||!ok2){
			auto v = make_pair(arr[nxt],nxt);
			brr.erase(brr.find(v));
			index.erase(index.find(u.second));
			score+=score2;
			arr[nxt]+=arr[u.second];
			brr.insert({arr[nxt],nxt});
			ans[u.second] = -1;
		}
		else if (ok2){
			brr.insert(u);
			u = *brr.begin();
			brr.erase(u);
			it = index.find(u.second);
			p = *prev(it);
			auto v = make_pair(arr[p],p);
			brr.erase(brr.find(v));
			score+=(getscore(u.second + 1,n) * (arr[p] + arr[u.second]) - getscore(p + 1,n) * arr[p] - getscore(u.second + 1,n) * arr[u.second]);
			index.erase(index.find(p));
			arr[u.second]+=arr[p];
			brr.insert({arr[u.second],u.second});
			ans[p] = -1;
		}
		if (score > answer){
			cur = ans;
			answer = score;
		}
	}
	cout<<answer<<'\n';
	for (auto x:cur){
		if (x!=-1)cout<<x<<' ';
	}
	cout<<'\n';
	return 0;
} 
/*
7 3
4 1 3 4 0 2 3
*/

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