結果
問題 |
No.2923 Mayor's Job
|
ユーザー |
![]() |
提出日時 | 2024-10-14 16:02:51 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 476 ms / 2,000 ms |
コード長 | 1,562 bytes |
コンパイル時間 | 3,359 ms |
コンパイル使用メモリ | 80,548 KB |
実行使用メモリ | 109,136 KB |
最終ジャッジ日時 | 2024-10-14 16:03:05 |
合計ジャッジ時間 | 6,679 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); long k = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); int[] h = new int[n]; for (int i = 0; i < n; i++) { h[i] = Integer.parseInt(sa[i]); } int[] x = new int[n]; int[] y = new int[n]; for (int i = 0; i < n; i++) { sa = br.readLine().split(" "); x[i] = Integer.parseInt(sa[0]); y[i] = Integer.parseInt(sa[1]); } br.close(); long k2 = k * k; List<List<Integer>> list = new ArrayList<>(n); PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.h - o2.h); for (int i = 0; i < n; i++) { list.add(new ArrayList<>()); Obj o = new Obj(); o.i = i; o.h = h[i]; que.add(o); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { long dx = x[i] - x[j]; long dy = y[i] - y[j]; if (dx * dx + dy * dy <= k2) { if (h[i] < h[j]) { list.get(i).add(j); } if (h[i] > h[j]) { list.get(j).add(i); } } } } int ans = n; while (!que.isEmpty()) { Obj o = que.poll(); List<Integer> wk = list.get(o.i); for (int i : wk) { if (h[i] > o.h) { ans--; break; } } } System.out.println(ans); } static class Obj { int i, h; } }