Submission #402363

---

Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <limits>
#include <tuple>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <climits>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <complex>
 
using namespace std;
 
typedef long long          ll;
typedef unsigned int       uint;
typedef unsigned long long ull;
static const double EPS = 1e-12;
static const double PI  = acos(-1.0);
 
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define REP(i,n)   for (int i=0;i<(int)(n);i++)
#define ALL(a)     (a).begin(),(a).end()
#define DEBUG(x)   cout<<#x<<": "<<x<<endl

int N;
vector<pair<int, int>> hs(100001);

bool check(ll m) {
  vector<double> t;
  REP(i, N) {
    t.push_back((double)(m - hs[i].first) / hs[i].second);
  }
  sort(ALL(t));
  REP(i, N) {
    if (i > t[i]) {
      return false;
    }
  }
  return true;
}

int main() {
  cin >> N;
  REP(i, N) {
    cin >> hs[i].first >> hs[i].second;
  }
  ll l = 0;
  ll h = 100000000000001LL;
  while (l <= h) {
    ll m = (l + h) / 2;
    if (check(m)) {
      h = m - 1;
    } else {
      l = m + 1;
    }
  }
  std::cout << l << std::endl;
}

Submission Info

Judge Result