Submission #402368

---

Source Code Expand

#include <iostream>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <algorithm>
#include <functional>
#include <limits.h>
#include <bitset>

#include <tuple>
#include <unordered_map>

#define mp       make_pair
#define mt       make_tuple
#define pb       push_back
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int N;
vector<int> h,s;
bool check(ll x){
	vector<ll> t(N);
	for (int i = 0; i < N; i++){
		if (x - h[i] < 0)return false;
		t[i] = (x - h[i]) / s[i];
	}
	sort(t.begin(), t.end());
	for (int i = 0; i < N; i++){
		if (t[i] < i)return false;
	}
	return true;
}
int main(){
	cin >> N;
	h.resize(N);
	s.resize(N);
	for (int i = 0; i < N; i++){
		cin >> h[i] >> s[i];
	}
	ll left,right;
	left = 0;
	right = 1LL << 50;
	while (right - left > 1){
		ll med = (right + left) / 2;
		if (check(med)){
			right = med;
		}else{
			left = med;
		}
	}
	cout << right << endl;
	return 0;
}

Submission Info

Judge Result