結果
問題 | No.2408 Lakes and Fish |
ユーザー |
|
提出日時 | 2023-08-11 22:06:42 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 4,203 ms |
コンパイル使用メモリ | 179,384 KB |
実行使用メモリ | 18,672 KB |
最終ジャッジ日時 | 2024-11-18 16:29:11 |
合計ジャッジ時間 | 7,041 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
import std; struct trio { int F; int B; int W; } void main () { int N, M; readln.read(N, M); int[] L = readln.split.to!(int[]); trio[] fish = new trio[](M); foreach (i; 0..M) { int F, B, W; readln.read(F, B, W); fish[i] = trio(F, B, W); } solve(N, M, L, fish); } void solve (int N, int M, int[] L, trio[] fish) { // ある魚について、水場に動かすべきかどうかを貪欲に取れば良い L.sort; bool[int] water; foreach (l; L) { water[l] = true; } long ans = 0; foreach (f; fish) { // すでに水の中にいるか? if (f.F in water) { ans += f.W; continue; } // 一番近い水場はどこか? int near; if (f.F < L[0]) { near = L[0]; } else if (L[$-1] < f.F) { near = L[$-1]; } else { int ok = 0, ng = cast(int) (L.length-1); while (1 < abs(ok-ng)) { int mid = (ok+ng) / 2; if (L[mid] < f.F) { ok = mid; } else { ng = mid; } } if (abs(f.F - L[ok]) < abs(f.F - L[ng])) { near = L[ok]; } else { near = L[ng]; } } ans += max(f.B, f.W - abs(near - f.F)); } writeln(ans); } void read(T...)(string S, ref T args) { auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } }