Submission #3214375

---

Source Code Expand

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++)
#define int long long
using namespace std;
using P = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int MOD = 1e9 + 7;

int N;
VI H, S;
bool ok(int x) {
  VI count(N, 0);
  REP (i, N) {
    if (x - H[i] < 0) { return false; }
    int tmp = (x - H[i]) / S[i];
    if (tmp < N) {
      count[tmp]++;
    }
  }
  REP (i, N-1) {
    if (count[i] > i+1) { return false; }
    count[i+1] += count[i];
  }
  return true;
}
signed main() {
  cin >> N;
  H.resize(N); S.resize(N);
  REP (i, N) {
    cin >> H[i] >> S[i];
  }
  int lb = -1;
  int ub = 1e18;
  while (ub - lb > 1) {
    int mid = (lb + ub) / 2;
    if (ok(mid)) {
      ub = mid;
    } else {
      lb = mid;
    }
  }
  cout << ub << endl;
}

Submission Info

Judge Result