제출 #884250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884250		pan	Feast (NOI19_feast)	C++17	0 / 100	116 ms	12868 KiB

feast

#include <bits/stdc++.h>


#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=1; 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];
		if (y.prev==-1)
		{
			ll n = y.next;
			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;
			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;
			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));
	}
	ll ans=0;
	
	for (ll i=0; i<food2.size(); ++i) 
	{
		if (food2[i].val>0) ans+=food2[i].val;
	}
	cout << ans;

	return 0;
}

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

feast.cpp: In function 'int main()':
feast.cpp:49: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]
   49 |  for (ll i=0; i<food.size();i++)
      |               ~^~~~~~~~~~~~
feast.cpp:74: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]
   74 |   else if (y.next==food2.size())
      |            ~~~~~~^~~~~~~~~~~~~~
feast.cpp:95: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]
   95 |  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