Submission #1287310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287310		Jawad_Akbar_JJ	Feast (NOI19_feast)	C++20	4 / 100	1096 ms	6532 KiB

feast

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long
const int N = 1<<19;
int a[N], Ans, final_Ans;

signed main(){
	int n, k, cur = 0;
	cin>>n>>k;

	vector<pair<int, int>> vec;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		if (cur == 0 or a[i] == 0)
			cur += a[i];
		else if ((cur < 0) == (a[i] < 0))
			cur += a[i];
		else{
			vec.push_back({cur, i});
			cur = a[i];
		}
	}
	if (cur > 0)
		vec.push_back({cur, n});
	if (vec.size() > 0 and vec[0].first < 0)
		vec.erase(begin(vec));

	while (1){

		vector<int> ansVec;
		for (int i=0;i<vec.size();i += 2)
			ansVec.push_back(vec[i].first);
		sort(begin(ansVec), end(ansVec));

		int kk = k;
		while (kk > 0 and ansVec.size() > 0)
			Ans += ansVec.back(), ansVec.pop_back(), kk--;

		final_Ans = max(final_Ans, Ans);

		int id = -1, mn = 1e17;
		for (int i=1;i<vec.size()-1;i += 2){
			if (-vec[i].first < min(vec[i+1].first, vec[i-1].first)){
				if (-vec[i].first <= mn)
					id = i, mn = -vec[i].first;
			}
		}

		if (id == -1 or ansVec.size() == 0)
			break;
		vec[id-1] = {vec[id+1].first + vec[id-1].first + vec[id].first, vec[id-1].second};
		vec.erase(begin(vec) + id);
		vec.erase(begin(vec) + id);
	}
	
	cout<<Ans<<'\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29