Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define max(a,b) ( ((a) > (b)) ? (a) : (b) )
- #define min(a,b) ( ((a) < (b)) ? (a) : (b) )
- #define fori(n) for (int i = 0; i < (n); i++)
- #define forj(n) for (int j = 0; j < (n); j++)
- #define FOR(a,b,c) for (int a = (b); a < (c); ++a)
- #define forfill(n,x) for (int zzz = 0; zzz < (n); zzz++) cin >> x[zzz]
- #define all(x) (x).begin(), (x).end()
- #define allr(x) (x).rbegin(), (x).rend()
- #define unsync cin.sync_with_stdio(false), cin.tie(0)
- #define inoutfile freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
- typedef long long lng;
- typedef pair<int, int> pii;
- typedef pair<lng, lng> pll;
- typedef vector<int> vi;
- typedef vector<vector<int>> vii;
- typedef vector<pair<int, int>> vpii;
- struct prob { int i; int a; int t; };
- int n, T;
- vector<prob> p;
- bool valid(int k, bool print = false) {
- int sum = 0;
- int c = 0;
- fori(n) {
- if (p[i].a >= k){
- sum += p[i].t;
- c++;
- if (sum > T) return false;
- if (print) cout << p[i].i << " ";
- if (c == k) return true;
- }
- }
- return false;
- }
- int main()
- {
- cin >> n >> T;
- p.resize(n);
- fori(n) {
- p[i].i = i + 1;
- cin >> p[i].a >> p[i].t;
- }
- sort(all(p), [](prob&x, prob&y) {return x.t < y.t; });
- int st = 0, en = 2e5;
- int mid;
- while (st < en) {
- mid = st + (en - st + 1) / 2;
- if (valid(mid))
- st = mid;
- else
- en = mid - 1;
- }
- cout << st << endl << st << endl;
- valid(st, true);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement