Submission #401344

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int64, int64 > Pi;
int main()
{
  int N;
  Pi data[100000];
  cin >> N;
  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    cin >> data[i].first >> data[i].second; 
    ret = max(ret, data[i].first);
  }

  int64 low = ret, high = 1LL << 40;

  while(high - low > 0) {
    int64 mid = (low + high) >> 1;
    vector< int64 > dat;
    for(int i = 0; i < N; i++) {
      int64 itu = mid - data[i].first;
      itu /= data[i].second;
      dat.push_back(itu);
    }
    sort(dat.begin(), dat.end());
    bool flag = true;
    int cnt = 0;
    for(int i = 0; i < dat.size(); i++) { // 切る時間
      if(i > dat[i]) flag = false; 
    }
    if(flag) high = mid;
    else low = mid + 1;
  }
  cout << low << endl;
}

Submission Info

Judge Result