oj.uz

Submission #884250

# Submission time Handle Problem Language Result Execution time Memory
884250 2023-12-07T03:34:30 Z pan Feast (NOI19_feast) C++17
0 / 100
 116 ms 12868 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 12868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -