Submission #402379

---

Source Code Expand

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]


N = n()
HS = []
for i in xrange(N):
    HS.append(ln())

from decimal import *

lb = 1
ub = 1e16
L = len(HS)
while ub - lb > 1:
    mid = int((ub + lb) / 2)
    temp = []
    bucket = [0] * L
    for h, s in HS:
        u = max(min(((mid - h) / s), L - 1), 0)
        bucket[u] += 1
    count = 0
    for i in xrange(L):
        if count > i:
            break
        count += bucket[i]
    else:
        ub = mid
        continue
    lb = mid

print ub

Submission Info

Judge Result