結果
問題 | No.2408 Lakes and Fish |
ユーザー | InTheBloom |
提出日時 | 2023-08-11 22:06:42 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 155 ms / 2,000 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 4,333 ms |
コンパイル使用メモリ | 178,560 KB |
実行使用メモリ | 16,948 KB |
最終ジャッジ日時 | 2024-04-29 13:05:06 |
合計ジャッジ時間 | 6,809 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 140 ms
16,900 KB |
testcase_05 | AC | 139 ms
16,948 KB |
testcase_06 | AC | 132 ms
16,756 KB |
testcase_07 | AC | 155 ms
11,260 KB |
testcase_08 | AC | 154 ms
11,256 KB |
testcase_09 | AC | 154 ms
11,256 KB |
testcase_10 | AC | 151 ms
11,260 KB |
testcase_11 | AC | 80 ms
12,024 KB |
testcase_12 | AC | 115 ms
16,180 KB |
testcase_13 | AC | 29 ms
5,376 KB |
testcase_14 | AC | 64 ms
8,968 KB |
testcase_15 | AC | 126 ms
16,072 KB |
testcase_16 | AC | 43 ms
7,444 KB |
testcase_17 | AC | 32 ms
5,376 KB |
testcase_18 | AC | 73 ms
10,268 KB |
testcase_19 | AC | 119 ms
15,520 KB |
testcase_20 | AC | 109 ms
12,416 KB |
testcase_21 | AC | 122 ms
15,716 KB |
ソースコード
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)); } }