| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 884268 |
2023-12-07T04:41:55 Z |
pan |
Feast (NOI19_feast) |
C++17 |
|
289 ms |
14772 KB |
#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 = nn;
food2[n].val = -1e10;
}
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 = pp;
food2[p].val = -1e10;
}
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;
food2[p].val = -1e10;
food2[n].val = -1e10;
}
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:45: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]
45 | for (ll i=0; i<food.size(); ++i) cout << food[i] << endl;
| ~^~~~~~~~~~~~
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:71: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]
71 | if (nn<food2.size()) food2[nn].prev=ind;
| ~~^~~~~~~~~~~~~
feast.cpp:77: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]
77 | else if (y.next==food2.size())
| ~~~~~~^~~~~~~~~~~~~~
feast.cpp:93: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]
93 | if (nn<food2.size()) food2[nn].prev=ind;
| ~~^~~~~~~~~~~~~
feast.cpp:108: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]
108 | for (ll i=0; i<food2.size(); ++i)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
289 ms |
14772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
