Submission #1948064

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int n, h;
vector<int> a, b;


bool f(int m){
    int sum = 0;
    rep(i, 0, n){
        if(b[i] < a[0]) continue;
        sum += b[i];
        m--;
        if(m == 0) break;
    }
    sum += m * a[0];
    return sum >= h;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> h;
    a.resize(n); b.resize(n);
    rep(i, 0, n){
        cin >> a[i] >> b[i];
    }
    sort(all(a));
    reverse(all(a));
    sort(all(b));
    reverse(all(b));
    int l = 0, r = 1e9 + 10;
    rep(i, 0, 100){
        int mid = (l + r) / 2;
        if(f(mid)) r = mid;
        else l = mid;
    }
    cout << r << endl;
}

Submission Info

Judge Result