Submission #814708

#	Time	Username	Problem	Language	Result	Execution time	Memory
814708		BamshooT	Feast (NOI19_feast)	C++14	100 / 100	167 ms	17388 KiB

feast

#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,int> ii;
const int N = 300005;
long long n, k, m = 1, a[N], L[N], R[N], cntD = 0;
set<ii> sf, sd;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >>n >>k;
	for(int i=1; i<=n; i++)
		cin >>a[i];
	m = 0;
	for(int i=1; i<=n; i++)
		if(a[i] != 0) a[++m] = a[i];
	n = m, m = 1;
	while (m <= n && a[m] < 0) m++;
	int u = 1;
	a[1] = a[m];
	for(int i=m+1; i<=n; i++)
		if(a[i]*a[i-1] > 0)
			a[u] += a[i];
		else
			a[++u] = a[i];
	if(a[u] < 0) u--;
	m = u;
	for(int i=1; i<=m; i++)
	{
		cntD += (a[i] > 0);
		sf.insert({abs(a[i]), i});
		L[i] = i-1, R[i] = i+1;
	}
	while(cntD > k)
	{
		int v = sf.begin()->first, i = sf.begin()->second;
		int x = L[i], y = R[i];
		sf.erase(sf.begin());
		if(L[i]==0 && a[i] <= 0)
			L[R[i]] = 0;
		else if(R[i]>m && a[i] <= 0)
			R[L[i]] = m+1;
		else if(L[i] >= 1 && R[i] <= m)
		{
			cntD--;
			sf.erase(sf.find({abs(a[x]), x}));
			sf.erase(sf.find({abs(a[y]), y}));
			a[x] = a[x] + a[i] + a[y];
			sf.insert({abs(a[x]), x});
			L[R[y]] = x, R[x] = R[y];
		}
		else if(L[i] >= 1)
		{
			cntD--;
			sf.erase(sf.find({abs(a[x]), x}));
			a[x] = a[x] + a[i];
			sf.insert({abs(a[x]), x});
			R[x] = m+1;
		}
		else if(R[i] <= m)
		{
			cntD--;
			sf.erase(sf.find({abs(a[y]), y}));
			a[i] = a[i] + a[y];
			sf.insert({abs(a[i]), i});
			L[R[y]] = i, R[i] = R[y];
		}
	}
	long long sum = 0;
	for(auto x : sf)
	{
		if(a[x.second] > 0)
			sum += x.first;
	}
	cout <<sum;
	return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:36:7: warning: unused variable 'v' [-Wunused-variable]
   36 |   int v = sf.begin()->first, i = sf.begin()->second;
      |       ^

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