Submission #1952607

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define ALL(c)  (c).begin(),(c).end()


ll solve(int N, ll H, vi& a, vi& b) {
    int best = 0x7fffffff;

    vector<int> z(ALL(b));
    sort(ALL(z)); reverse(ALL(z));

    vector<ll> ac(N+1, 0);
    rep(i,N) ac[i+1] = ac[i] + z[i]; // どこかでHを超えるかも

    int ai = *max_element(ALL(a));
    rep(i, N+1) {
        ll rem = H - ac[i];
        if (rem > 0) {
            int pls = (rem + ai - 1) / ai;
            best = min(best, i + pls);
        } else {
            best = min(best, i);
        }
    }
    return best;
}

int main() {
    int N, H; cin >> N >> H;
    vector<int> a(N), b(N);
    rep(i, N){
        cin >> a[i] >> b[i];
    }
    cout << solve(N, H, a, b) << endl;
    return 0;
}

Submission Info

Judge Result