結果

問題 No.2408 Lakes and Fish
ユーザー norioc
提出日時 2025-06-10 23:31:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 280 ms / 2,000 ms
コード長 743 bytes
コンパイル時間 517 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 105,284 KB
最終ジャッジ日時 2025-06-10 23:31:12
合計ジャッジ時間 7,074 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left


def find_nearest(a: list[int], v: int) -> int:
    """ソート済みリスト a の要素のうち、v との差が最も小さい要素を返す"""
    assert len(a) > 0

    p = bisect_left(a, v)
    if p == len(a):
        return a[-1]

    if p > 0 and v-a[p-1] <= a[p]-v:
        return a[p-1]
    return a[p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
xs = []
for _ in range(M):
    F, B, W = map(int, input().split())
    xs.append((F, B, W))

lakes = set(L)
ans = 0
for f, b, w in xs:
    t = 0
    if f in lakes:
        t = w
    else:
        t = b
        # 水に移動する
        d = abs(f - find_nearest(L, f))
        t = max(t, w - d)

    ans += t

print(ans)
0