Submission #542783

#	Time	Username	Problem	Language	Result	Execution time	Memory
542783		shcal	Balloons (CEOI11_bal)	Java	70 / 100	2065 ms	33608 KiB

bal

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Stack;
import java.util.StringTokenizer;

// https://oj.uz/problem/view/CEOI11_bal
public class bal {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		
		int n = Integer.parseInt(br.readLine());
		
		Stack<Integer> s = new Stack<>();
		
		double[] px = new double[n];
		double[] pr = new double[n];
		
		StringTokenizer token;
		for (int i = 0; i < n; i++) {
			token = new StringTokenizer(br.readLine());
			double x = Double.parseDouble(token.nextToken());
			double r = Double.parseDouble(token.nextToken());
			
			while (!s.isEmpty()) {
				int t = s.peek();
				double x1 = px[t];
				double r1 = pr[t];
				r = Math.min(r, (x-x1)*(x-x1)/(4.0*r1));
				if (r >= r1) s.pop();
				else break;
			}
			
			out.printf("%.3f\n", r);
			
			px[i] = x;
			pr[i] = r;
			s.push(i);
		}
		
		out.close();
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 0 / 10