Submission #1066701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066701		Oz121	Balloons (CEOI11_bal)	Java	100 / 100	1702 ms	43408 KiB

bal

import java.io.*;
import java.util.*;
public class bal {
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine()); int num = Integer.parseInt(l1.nextToken()); double[][] arr = new double[num][2];
        for (int i = 0;i<num;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> idx = new Stack<>(); double[] ans = new double[num];
        for (int i = 0;i<num;i++) {
            double newR = arr[i][1];
            while (!idx.isEmpty()) {
                int j = idx.peek();
                double maxR = Math.pow(arr[i][0]-arr[j][0],2)/(4*ans[j]);

                if (maxR>arr[i][1]) {
                    if (arr[i][1]<=ans[j]) {
                        idx.add(i); break;
                    }
                    else idx.pop();
                } else { //maxR<=arr[i][1]
                    newR = Math.min(newR, maxR);
                    if (newR<=ans[j]) {
                        idx.add(i);
                        break;
                    }
                    else idx.pop();
                }
            }

            ans[i] = newR;
            idx.add(i);
        }

        for (double i : ans) 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