Submission #824214

#	Time	Username	Problem	Language	Result	Execution time	Memory
824214		powervic08	Balloons (CEOI11_bal)	Java	100 / 100	1521 ms	35516 KiB

bal

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

public class bal {

    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = Integer.parseInt(f.readLine());
        double[] rad = new double[n];
        Stack<Balloon> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(f.readLine());
            int x = Integer.parseInt(st.nextToken());
            double r = Double.parseDouble(st.nextToken());
            if (stack.isEmpty()) {
                rad[i] = r;
                stack.push(new Balloon(x, r));
                continue;
            }
            // c1 = (a, b) c2 = (c, d)
            // d = (c - a) ^ 2 / 4b
            double cur = -1;
            while (!stack.isEmpty()) {
                Balloon b = stack.peek();
                if (cur == -1) {
                    cur = Math.pow((x - b.pos), 2) / 4 / b.rad;
                }
                else {
                    cur = Math.min(cur, Math.pow((x - b.pos), 2) / 4 / b.rad);
                }
                cur = Math.min(cur, r);
                if (cur >= b.rad) {
                    stack.pop();
                }
                else {
                    break;
                }
            }
            rad[i] = cur;
            stack.push(new Balloon(x, cur));
        }
        for (double d : rad) {
            out.printf("%.3f%n", d);
        }
        out.close();
        f.close();
    }

    static class Balloon {
        double rad;
        int pos;

        public Balloon(int a, double b) {
            rad = b;
            pos = a;
        }
    }

}

• 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