Submission #682706

#	Time	Username	Problem	Language	Result	Execution time	Memory
682706		bruhgamer	Mobile (BOI12_mobile)	Java	0 / 100	905 ms	86152 KiB

mobile

//package USACO;
import java.util.*;
import java.io.*;
public class mobile {
	public static long search(long start, long end) {
		if(start == end) {
			return start;
		}
		long mid = (start + end - 1)/2;
		if(works(mid)) {
			return search(start, mid);
		}
		return search(mid+1,end);
	}
	public static int n;
	public static int l;
	public static long[][]arr;
	public static boolean works(long dis) {
		long to  = 0;
		for(int i = 0; i < n; i++) {
			long disx = (long) Math.sqrt(dis - (arr[i][1] * arr[i][1]));
			long disxstart = arr[i][0] - disx;
			long disxend = arr[i][0] + disx;
			if(disxstart > (to+1)) {
				return false;
			}
			to = Math.max(disxend, to);
		}
		return to >= l;
	}
	public static void main(String[]args) throws IOException{
		Kattio io = new Kattio();
		n = io.nextInt();
		l = io.nextInt();
		arr = new long[n][2];
		for(int i = 0; i < n; i++) {
			arr[i][0] = io.nextLong();
			arr[i][1] = io.nextLong();
		}
		long val = search(0L, Long.MAX_VALUE);
		//io.println(val);
		io.println(Math.sqrt(val));
		io.close();
	}
	static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st;
		// standard input
		public Kattio() { this(System.in, System.out); }
		public Kattio(InputStream i, OutputStream o) {
			super(o);
			r = new BufferedReader(new InputStreamReader(i));
		}
		// USACO-style file input
		public Kattio(String problemName) throws IOException {
			super(problemName + ".out");
			r = new BufferedReader(new FileReader(problemName + ".in"));
		}
		// returns null if no more input
		public String next() {
			try {
				while (st == null || !st.hasMoreTokens())
					st = new StringTokenizer(r.readLine());
				return st.nextToken();
			} catch (Exception e) { }
			return null;
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
		
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5