Submission #800858

#	Time	Username	Problem	Language	Result	Execution time	Memory
800858		Callie	Balloons (CEOI11_bal)	Java	100 / 100	1636 ms	34024 KiB

bal

import java.io.*;
import java.util.*;

class Balloon {
	public long x;
	public double r;

	public Balloon(long x, double r) {
		this.x = x;
		this.r = r;
	}

	public double calcR(long bx) { 
		return (x - bx) * (x - bx) / (4 * r); 
	}
}

public class bal {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int balloons = Integer.parseInt(in.readLine());
		double[] answers = new double[balloons];
		Stack<Balloon> s = new Stack<Balloon>();
		
		for(int i = 0; i < balloons; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			long x = Integer.parseInt(st.nextToken());
			double r = Integer.parseInt(st.nextToken());
			double max = r;
			
			while(!s.isEmpty()) {			
				double to = s.peek().calcR(x);			
				max = Math.min(max, to);
				
				if(max >= s.peek().r) {
					s.pop();
					continue;
				}
				else break;
			}
			
			s.add(new Balloon(x, max));
			answers[i] = max;
		}
		
		for(double i: answers) System.out.println(i);
	}
}

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