結果
問題 |
No.1012 荷物収集
|
ユーザー |
|
提出日時 | 2022-10-27 19:22:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 389 ms / 2,000 ms |
コード長 | 588 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 109,696 KB |
最終ジャッジ日時 | 2024-07-05 04:54:40 |
合計ジャッジ時間 | 13,721 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
INF = 1 << 30 import bisect as bs n, q = map(int, input().split()) items = [list(map(int, input().split())) for _ in range(n)] items.append([- INF, 0]) items.append([INF, 0]) items.sort(key=lambda x: x[0]) xs = [items[i][0] for i in range(len(items))] xws = [0 for _ in range(n + 2)] ws = [0 for _ in range(n + 2)] for i in range(1, n + 2): xi, wi = items[i] xws[i] = xws[i - 1] + xi * wi ws[i] = ws[i - 1] + wi queries = list(map(int, input().split())) for i in range(q): k = bs.bisect_right(xs, queries[i]) print(xws[n] - 2 * xws[k - 1] + queries[i] * (2 * ws[k - 1] - ws[n]))