#include <stdio.h>
#include <map>
#include <set>
long long A[200005];
std::map<int, long long> V;
std::set<std::pair<long long, int> > PQ;
// bool operator<(std::pair<long long, int> a, std::pair<long long, int> b)
// {
// return (a.first < b.first || (a.first == b.first && a.second < b.second));
// }
int main()
{
int N;
scanf("%d", &N);
int i;
for (i = 0; i < N; i++)
{
scanf("%lld", &A[i]);
V.insert({i, A[i]});
PQ.insert({-A[i], i});
}
long long sum = 0, r, diff;
std::map<int, long long>::iterator p, q;
std::set<std::pair<long long, int> >::iterator it;
int s;
for (i = 1; i <= (N + 1)/2; i++)
{
// for (p = V.begin(); p != V.end(); p++)
// printf("V %d %lld\n", p->first, p->second);
// for (it = PQ.begin(); it != PQ.end(); it++)
// printf("PQ %lld %d\n", (*it).first, (*it).second);
r = -PQ.begin()->first;
s = PQ.begin()->second;
diff = 0;
PQ.erase(PQ.begin());
sum += r;
p = V.find(s);
if (p != V.begin())
{
p--;
diff += p->second;
s = p->first;
PQ.erase({-p->second, p->first});
p = V.erase(p);
}
diff -= p->second;
p = V.erase(p);
if (p != V.end())
{
diff += p->second;
PQ.erase({-p->second, p->first});
p = V.erase(p);
}
V.insert({s, diff});
PQ.insert({-diff, s});
printf("%lld\n", sum);
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
candies.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &A[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
