結果
問題 |
No.2923 Mayor's Job
|
ユーザー |
![]() |
提出日時 | 2024-10-14 15:59:58 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,607 bytes |
コンパイル時間 | 3,034 ms |
コンパイル使用メモリ | 81,544 KB |
実行使用メモリ | 354,344 KB |
最終ジャッジ日時 | 2024-10-14 16:00:11 |
合計ジャッジ時間 | 12,767 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 TLE * 1 |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.PriorityQueue; import java.util.Set; 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<Set<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 HashSet<>()); 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) { list.get(i).add(j); list.get(j).add(i); } } } int ans = n; while (!que.isEmpty()) { Obj o = que.poll(); Set<Integer> set = list.get(o.i); for (int i : set) { if (h[i] > o.h) { ans--; for (int j : set) { list.get(j).remove(o.i); } break; } } } System.out.println(ans); } static class Obj { int i, h; } }