Advertisement
Guest User

Untitled

a guest
Feb 10th, 2016
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class cow {
  5. public:
  6. int milk, time;
  7. } cows[10010];
  8.  
  9. bool cmp(const cow& a, const cow& b) {
  10. if (a.milk == b.milk)
  11. return a.time < b.time;
  12. return a.milk > b.milk;
  13. }
  14.  
  15. int* freq;
  16.  
  17. void update(int val, int pos) {
  18. while (pos <= 10010) {
  19. freq[pos] += val;
  20. pos += (pos & (-pos));
  21. }
  22. }
  23.  
  24. int query(int pos) {
  25. int ans = 0;
  26. while (pos > 0) {
  27. ans += freq[pos];
  28. pos -= (pos & (-pos));
  29. }
  30. return ans;
  31. }
  32.  
  33. int main(void) {
  34. int n;
  35. scanf("%d", &n);
  36. freq = (int*) calloc(10010, sizeof(int));
  37. int mt = 0;
  38. for (int i = 0; i < n; i++) {
  39. scanf("%d %d", &cows[i].milk, &cows[i].time);
  40. mt = max(mt, cows[i].time);
  41. }
  42. sort(cows, cows+n, cmp);
  43. //for (int i = 0; i < n; i++) {
  44. // printf("%d %d\n", cows[i].milk, cows[i].time);
  45. //}
  46. int count = 0, id = 0;
  47. int ans = 0, allowed = 0;
  48. while (count < mt && id < n) {
  49. if (query(cows[id].time) < cows[id].time) {
  50. ans += cows[id].milk;
  51. update(1, cows[id].time);
  52. count++;
  53. }
  54. id++;
  55. }
  56. printf("%d\n", ans);
  57. return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement