Advertisement
Emiliatan

c824

May 23rd, 2019
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. /* c824              */
  2. /* AC (0.6s, 31.6MB) */
  3. #include <cstdio>
  4. #include <queue>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8.  
  9. typedef long long int64;
  10.  
  11. struct node
  12. {
  13.     int poww;
  14.     int64 val;
  15. };
  16. struct cmp
  17. {
  18.     bool operator() (const node &lhs, const node &rhs)
  19.     {
  20.         return (lhs.poww > rhs.poww) || (lhs.poww == rhs.poww && lhs.val < rhs.val);
  21.     }
  22. };
  23.  
  24. typedef std::priority_queue<node, vector<node>, cmp> heap;
  25. int N, M, sum;
  26. node tmp;
  27. heap pq;
  28.  
  29. int main()
  30. {
  31.     scanf("%d %d", &N, &M);
  32.     for(int i = 0; i < N && scanf("%d %lld", &tmp.poww, &tmp.val); ++i)
  33.         if(tmp.poww > M) continue;
  34.         else pq.emplace(move(tmp));
  35.  
  36.     tmp.poww = M, tmp.val = 0;
  37.  
  38.     while(pq.size() > 1)
  39.     {
  40.         tmp = pq.top(); pq.pop();
  41.         if(tmp.poww == M) break;
  42.  
  43.         if(tmp.poww == pq.top().poww)
  44.         {
  45.             tmp.val += pq.top().val;
  46.             ++tmp.poww;
  47.             pq.pop();
  48.         }
  49.         else tmp.poww = pq.top().poww;
  50.  
  51.         pq.emplace(move(tmp));
  52.     }
  53.  
  54.     printf("%lld", tmp.val);
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement