Submission #401346

---

Source Code Expand

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long h[]=new long[114514];
		long s[]=new long[114514];
		int num[]=new int[114514];
		Scanner scan=new Scanner(System.in);
		long lo=1,hi=1145141919810893L;
		int n=scan.nextInt(),i;
		for(i=0;i<n;i++){
			h[i]=scan.nextInt();
			s[i]=scan.nextInt();
			lo=Math.max(lo, h[i]);
		}
		while(hi>lo){
			long mi=(hi+lo)/2;
			for(i=0;i<n;i++) num[i]=0;
			for(i=0;i<n;i++){
				long t=(mi-h[i])/s[i];
				t=Math.min(t, n-1);
				num[(int)t]++;
			}
			int sum=0,f=0;
			for(i=0;i<n;i++){
				sum+=num[i];if(sum>i+1) f=1;
			}
			if(f>0) lo=mi+1;else hi=mi;
		}
		System.out.println(lo);
	}

}

Submission Info

Judge Result