Hello Codeforces! I've been struggling with this problem for half an hour, I've been testing it but I couldn't find the wrong one. Can you help me? UPD: I solved the problem,Thanks. Reason: I couldn't get all the positive numbers.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Hello Codeforces! I've been struggling with this problem for half an hour, I've been testing it but I couldn't find the wrong one. Can you help me? UPD: I solved the problem,Thanks. Reason: I couldn't get all the positive numbers.
Название |
---|
Though I really can't understand what you are trying to do but may be you are thinking too much.
if its a bonus card store it somewhere.
if its a hero card pick the max bonus card and give it to hero and discard that card.
The main vision of the problem is make sure you know how to pick max element of a deck(List) in most suitable time complexity. Just think of a data structure that does the job.
Your code gives the wrong answer for the following test case:
Instead of doing what you're doing, it'd be simpler to simply maintain a priority queue / multiset of all elements and remove the largest one everytime you encounter a hero. Like this.
The main approach in this question is that as we are getting the positive values we will store them in a priority queue so that maximum remain at the top , but as soon a 0 is encountered, then we get the top value of pq and add that to our result and then discard it, now the reason we are taking a priority queue for this question is that since we want the maximum score, so essentially we are discarding the ones that are least and are not needed. Now you may be thinking instead of taking priority queue why don't we just use a max variable that will store the maximum of values in a sequence where 0 is not there and then as soon as 0 comes we will add the max to our result, but the reason this approach will fail is because, if say two consecutive 0's comes, then for the first 0 we will use the max, but for the second 0 we won't have any data about the second maximum, similarly if a lot of 0s comes then we will need to store data of all values in decreasing order, and hence it is better to just use priority queue for faster insertion and deletion.
here is the code for this question, -------------------------------------------------------------------------------------------------------------- void solve(){ ll n; cin>>n; priority_queue pq; ll ans = 0; for(int i=0; i<n; i++){ ll val; cin>>val; if(val == 0){ if(!pq.empty()){ ans += pq.top(); pq.pop(); } } else{ pq.push(val); } } cout<<ans<<endl; }
Auto comment: topic has been updated by Tmmaster (previous revision, new revision, compare).
using multiset :(https://mirror.codeforces.com/contest/1800/submission/260698743)