結果
問題 |
No.1012 荷物収集
|
ユーザー |
![]() |
提出日時 | 2020-03-26 17:51:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 452 ms / 2,000 ms |
コード長 | 622 bytes |
コンパイル時間 | 353 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 119,308 KB |
最終ジャッジ日時 | 2025-01-02 02:55:36 |
合計ジャッジ時間 | 12,641 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
import sys reader = (s.rstrip() for s in sys.stdin) input = reader.__next__ n,q = map(int, input().split()) x_set = set() xw = [] for i in range(n): x,w = map(int, input().split()) x_set.add(x) xw.append([x,w]) xw.sort() dd = sorted(x_set) xs = list(map(int, input().split())) w_sum = [0] xw_sum = [0] for x,w in xw: w_sum.append(w_sum[-1] + w) xw_sum.append(xw_sum[-1] + x*w) from bisect import bisect_left ans = [] for xi in xs: j = bisect_left(dd, xi) cost = w_sum[j]*xi - xw_sum[j] cost += (xw_sum[-1]-xw_sum[j]) - (w_sum[-1]-w_sum[j])*xi ans.append(cost) print(*ans, sep="\n")