Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- class cow {
- public:
- int milk, time;
- } cows[10010];
- bool cmp(const cow& a, const cow& b) {
- if (a.milk == b.milk)
- return a.time < b.time;
- return a.milk > b.milk;
- }
- int* freq;
- void update(int val, int pos) {
- while (pos <= 10010) {
- freq[pos] += val;
- pos += (pos & (-pos));
- }
- }
- int query(int pos) {
- int ans = 0;
- while (pos > 0) {
- ans += freq[pos];
- pos -= (pos & (-pos));
- }
- return ans;
- }
- int main(void) {
- int n;
- scanf("%d", &n);
- freq = (int*) calloc(10010, sizeof(int));
- int mt = 0;
- for (int i = 0; i < n; i++) {
- scanf("%d %d", &cows[i].milk, &cows[i].time);
- mt = max(mt, cows[i].time);
- }
- sort(cows, cows+n, cmp);
- //for (int i = 0; i < n; i++) {
- // printf("%d %d\n", cows[i].milk, cows[i].time);
- //}
- int count = 0, id = 0;
- int ans = 0, allowed = 0;
- while (count < mt && id < n) {
- if (query(cows[id].time) < cows[id].time) {
- ans += cows[id].milk;
- update(1, cows[id].time);
- count++;
- }
- id++;
- }
- printf("%d\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement