Submission #884253

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884253	2023-12-07T03:57:13 Z	pan	Feast (NOI19_feast)	C++17	12 / 100	127 ms	12944 KB

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

feast.cpp: In function 'int main()':
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: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
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	404 KB	Output is correct
2	Correct	80 ms	408 KB	Output is correct
3	Correct	80 ms	404 KB	Output is correct
4	Correct	83 ms	348 KB	Output is correct
5	Correct	79 ms	404 KB	Output is correct
6	Correct	101 ms	600 KB	Output is correct
7	Correct	82 ms	592 KB	Output is correct
8	Correct	79 ms	348 KB	Output is correct
9	Correct	78 ms	348 KB	Output is correct
10	Correct	79 ms	344 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	344 KB	Output is correct
2	Correct	43 ms	344 KB	Output is correct
3	Correct	41 ms	412 KB	Output is correct
4	Correct	42 ms	348 KB	Output is correct
5	Correct	88 ms	348 KB	Output is correct
6	Correct	41 ms	344 KB	Output is correct
7	Correct	42 ms	348 KB	Output is correct
8	Correct	80 ms	412 KB	Output is correct
9	Correct	84 ms	404 KB	Output is correct
10	Correct	42 ms	348 KB	Output is correct

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	436 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	348 KB	Output isn't correct
5	Halted	0 KB	-

Subtask #5
0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	436 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	348 KB	Output isn't correct
5	Halted	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	436 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	348 KB	Output isn't correct
5	Halted	0 KB	-

Subtask #7
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	404 KB	Output is correct
2	Correct	80 ms	408 KB	Output is correct
3	Correct	80 ms	404 KB	Output is correct
4	Correct	83 ms	348 KB	Output is correct
5	Correct	79 ms	404 KB	Output is correct
6	Correct	101 ms	600 KB	Output is correct
7	Correct	82 ms	592 KB	Output is correct
8	Correct	79 ms	348 KB	Output is correct
9	Correct	78 ms	348 KB	Output is correct
10	Correct	79 ms	344 KB	Output is correct
11	Correct	41 ms	344 KB	Output is correct
12	Correct	43 ms	344 KB	Output is correct
13	Correct	41 ms	412 KB	Output is correct
14	Correct	42 ms	348 KB	Output is correct
15	Correct	88 ms	348 KB	Output is correct
16	Correct	41 ms	344 KB	Output is correct
17	Correct	42 ms	348 KB	Output is correct
18	Correct	80 ms	412 KB	Output is correct
19	Correct	84 ms	404 KB	Output is correct
20	Correct	42 ms	348 KB	Output is correct
21	Incorrect	127 ms	12944 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Submission #884253

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 8.0 / 8.0

Subtask #3 0 / 18.0

Subtask #4 0 / 10.0

Subtask #5 0 / 11.0

Subtask #6 0 / 20.0

Subtask #7 0 / 29.0

Subtask #1
4.0 / 4.0

Subtask #2
8.0 / 8.0

Subtask #3
0 / 18.0

Subtask #4
0 / 10.0

Subtask #5
0 / 11.0

Subtask #6
0 / 20.0

Subtask #7
0 / 29.0