ABC 23 D - 射撃王 ( Binary search )

D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder
Search for the minimum height that is possible. Judge by the deadline, which should be pre-calculated and sorted.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXH = 1e9 + 9;
const int MAXS = 1e9 + 9;
typedef long long ll;

int n;
int h[ MAXN ], s[ MAXN ];

bool ok(ll x){
    vector<ll> dl( n ); // deadline
    for(int i = 0; i < n; ++i)
        dl[ i ] = ( x - h[ i ] ) / s[ i ];
    sort( dl.begin(), dl.end() );
    for(int i = 0; i < n; ++i)
        if( dl[ i ] < i )
            return false;
    return true;
}

void solve(){
    ll lb = *max_element( h, h + n ), ub = (ll)( 1e16 );
    ll ans = -1;
    while( lb <= ub ){
        ll mid = ( lb + ub ) / 2;
        if( ok( mid ) ) ans = mid, ub = mid - 1;
        else lb = mid + 1;
    }
    printf("%lld\n", ans);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &h[ i ], &s[ i ]);
    solve();
    return 0;
}