Advertisement
Guest User

Untitled

a guest
Jun 20th, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define max(a,b) ( ((a) > (b)) ? (a) : (b) )
  5. #define min(a,b) ( ((a) < (b)) ? (a) : (b) )
  6. #define fori(n) for (int i = 0; i < (n); i++)
  7. #define forj(n) for (int j = 0; j < (n); j++)
  8. #define FOR(a,b,c) for (int a = (b); a < (c); ++a)
  9. #define forfill(n,x) for (int zzz = 0; zzz < (n); zzz++) cin >> x[zzz]
  10. #define all(x) (x).begin(), (x).end()
  11. #define allr(x) (x).rbegin(), (x).rend()
  12. #define unsync cin.sync_with_stdio(false), cin.tie(0)
  13. #define inoutfile freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
  14.  
  15. typedef long long lng;
  16. typedef pair<int, int> pii;
  17. typedef pair<lng, lng> pll;
  18. typedef vector<int> vi;
  19. typedef vector<vector<int>> vii;
  20. typedef vector<pair<int, int>> vpii;
  21.  
  22. struct prob { int i; int a; int t; };
  23. int n, T;
  24. vector<prob> p;
  25.  
  26. bool valid(int k, bool print = false) {
  27.     int sum = 0;
  28.     int c = 0;
  29.     fori(n) {
  30.         if (p[i].a >= k){
  31.             sum += p[i].t;
  32.             c++;
  33.             if (sum > T) return false;
  34.             if (print) cout << p[i].i << " ";
  35.             if (c == k) return true;
  36.         }
  37.     }
  38.     return false;
  39. }
  40.  
  41. int main()
  42. {
  43.  
  44.     cin >> n >> T;
  45.     p.resize(n);
  46.     fori(n) {
  47.         p[i].i = i + 1;
  48.         cin >> p[i].a >> p[i].t;
  49.     }
  50.     sort(all(p), [](prob&x, prob&y) {return x.t < y.t; });
  51.  
  52.     int st = 0, en = 2e5;
  53.     int mid;
  54.     while (st < en) {
  55.         mid = st + (en - st + 1) / 2;
  56.         if (valid(mid))
  57.             st = mid;
  58.         else
  59.             en = mid - 1;
  60.     }
  61.     cout << st << endl << st << endl;
  62.     valid(st, true);
  63.  
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement