제출 #884343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884343		pan	Feast (NOI19_feast)	C++17	100 / 100	136 ms	16576 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;
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));
	}
	vector<bool> valid(food2.size(), true);
	for (ll i=0; i<nowk-k; ++i)
	{
		//cout << "running " << i << endl;
		while (!valid[pq.top().second] || abs(food2[pq.top().second].val)!=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)
		{
			if (y.val>0)
			{
				ll n = y.next;
				ll nn = food2[n].next;
				if (nn<food2.size()) food2[nn].prev=-1;
				valid[ind] = false;
				valid[n]=false;
				
				
			}
			else
			{
				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 = nn;
				valid[n] = false;
				pq.push(mp(abs(food2[ind].val), ind));
			}
		}
		else if (y.next==food2.size())
		{
			if (y.val>0)
			{
				ll p = y.prev;
				ll pp = food2[p].prev;
				if (pp>=0) food2[pp].next=food2.size();
				valid[ind] = false;
				valid[p]= false;
			}
			else
			{
				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 = pp;
				valid[p] = false;
				pq.push(mp(abs(food2[ind].val), ind));
			}
		}
		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 = pp;
			food2[ind].next = nn;
			valid[p] = false;
			valid[n]=false;
			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 (valid[i] && food2[i].val>0) {ans+=food2[i].val;}
	}
	cout << ans;

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

feast.cpp: In function 'int main()':
feast.cpp:50: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]
   50 |  for (ll i=0; i<food.size();i++)
      |               ~^~~~~~~~~~~~
feast.cpp:75:11: 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]
   75 |     if (nn<food2.size()) food2[nn].prev=-1;
      |         ~~^~~~~~~~~~~~~
feast.cpp:85:11: 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]
   85 |     if (nn<food2.size()) food2[nn].prev=ind;
      |         ~~^~~~~~~~~~~~~
feast.cpp:93: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]
   93 |   else if (y.next==food2.size())
      |            ~~~~~~^~~~~~~~~~~~~~
feast.cpp:121: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]
  121 |    if (nn<food2.size()) food2[nn].prev=ind;
      |        ~~^~~~~~~~~~~~~
feast.cpp:137: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]
  137 |  for (ll i=0; i<food2.size(); ++i)
      |               ~^~~~~~~~~~~~~

• 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