Submission #884252

#	Time	Username	Problem	Language	Result	Execution time	Memory
884252		pan	Feast (NOI19_feast)	C++17	0 / 100	1010 ms	18860 KiB

feast

#include <iostream>
#include <queue>
#include <vector>
#include <climits>


#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef long long ll;
struct node 
{
	ll prev, next, val;
};

struct compare
{
	bool operator() (pi const& a, pi const& b)
	{
		return a.first>b.first;
	}
};

int main()
{
	ll n,k,x;
	cin >> n >> k;
	vector<ll> food;
	for (ll i=0; i<n; ++i)
	{
		cin >> x;
		if (x==0) continue;
		if (!food.empty() && ((x<0 && food.back()<0 ) || (x>0 && food.back()>0)))
		{
			food[food.size()-1]+=x;
		}
		else
		{
			food.push_back(x);
		}
	}
	if (food[0]<0) food.erase(food.begin());
	if (food.back()<0) food.pop_back();
	
	for (ll i=0; i<food.size(); ++i) cout << food[i] << endl;
	ll nowk = (food.size()+1)/2;
	priority_queue<pi, vector<pi>, compare> pq;
	vector<node> food2;
	for (ll i=0; i<food.size();i++)
	{
		node y;
		y.prev=i-1, y.next = i+1, y.val = food[i];
		food2.pb(y);
		pq.push(mp(abs(food[i]),i));
	}
	for (ll i=0; i<nowk-k; ++i)
	{
		//cout << "running " << i << endl;
		while (abs(food2[pq.top().second].val)!=abs(pq.top().first))
		{
			pq.pop();
		}
		ll ind=pq.top().second;
		pq.pop();
		node y= food2[ind];
		//cout << "prev is " << y.prev << "next is " << y.next << endl;
		if (y.prev==-1)
		{
			ll n = y.next;
			ll nn = food2[n].next;
			if (nn<food2.size()) food2[nn].prev=ind;
			food2[ind].val+=food2[n].val;
			food2[ind].prev = -1;
			food2[ind].next = food2[n].next;
			food2[n].val = -LLONG_MAX;
		}
		else if (y.next==food2.size())
		{
			ll p = y.prev;
			ll pp = food2[p].prev;
			if (pp>=0) food2[pp].next=ind;
			food2[ind].val+=food2[p].val;
			food2[ind].next = food2.size();
			food2[ind].prev = food2[p].next;
			food2[p].val = -LLONG_MAX;
		}
		else
		{
			ll p = y.prev, n = y.next;
			ll nn = food2[n].next;
			ll pp = food2[p].prev;
			if (pp>=0) food2[pp].next=ind;
			if (nn<food2.size()) food2[nn].prev=ind;
			food2[ind].val+=food2[p].val+food2[n].val;
			food2[ind].prev = food2[p].prev;
			food2[ind].next = food2[n].next;
			food2[p].val = -LLONG_MAX;
			food2[n].val = -LLONG_MAX;
		}
		pq.push(mp(abs(food2[ind].val), ind));
		for (ll i=0; i<food2.size(); ++i) cout << food2[i].val  << endl;
		//cout << "Now pointing to " << food2[ind].prev  << " and " <<food2[ind].next << endl;
		
	}
	
	ll ans=0;
	
	for (ll i=0; i<food2.size(); ++i) 
	{
		if (food2[i].val>0) ans+=food2[i].val;
	}
	cout << ans;

	return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:48:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (ll i=0; i<food.size(); ++i) cout << food[i] << endl;
      |               ~^~~~~~~~~~~~
feast.cpp:52:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (ll i=0; i<food.size();i++)
      |               ~^~~~~~~~~~~~
feast.cpp:74:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    if (nn<food2.size()) food2[nn].prev=ind;
      |        ~~^~~~~~~~~~~~~
feast.cpp:80:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   else if (y.next==food2.size())
      |            ~~~~~~^~~~~~~~~~~~~~
feast.cpp:96:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    if (nn<food2.size()) food2[nn].prev=ind;
      |        ~~^~~~~~~~~~~~~
feast.cpp:104:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for (ll i=0; i<food2.size(); ++i) cout << food2[i].val  << endl;
      |                ~^~~~~~~~~~~~~
feast.cpp:111:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for (ll i=0; i<food2.size(); ++i)
      |               ~^~~~~~~~~~~~~

• Subtask 1: 0 / 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