結果
問題 | No.1012 荷物収集 |
ユーザー |
![]() |
提出日時 | 2020-03-21 04:38:35 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 835 ms / 2,000 ms |
コード長 | 658 bytes |
コンパイル時間 | 412 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 48,324 KB |
最終ジャッジ日時 | 2024-12-16 10:06:36 |
合計ジャッジ時間 | 20,121 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
N,Q=map(int,input().split()) B=[tuple(map(int,input().split())) for i in range(N)] X=list(map(int,input().split())) B.append((0,0)) B.append((1<<30,0)) N+=2 from operator import itemgetter B.sort(key=itemgetter(0)) LSUM=[0] for x,w in B: LSUM.append(LSUM[-1]+w) LC=[0] for i in range(1,N): LC.append(LC[-1]+(B[i][0]-B[i-1][0])*LSUM[i]) RSUM=[0] for x,w in B[::-1]: RSUM.append(RSUM[-1]+w) RC=[0] for i in range(N-1,0,-1): RC.append(RC[-1]+(B[i][0]-B[i-1][0])*RSUM[N-i]) LC.append(0) RC.append(0) import bisect for x in X: t=bisect.bisect_left(B,(x,1<<30)) print(LC[t-1]+LSUM[t]*(x-B[t-1][0])+RC[N-1-t]+RSUM[N-t]*(B[t][0]-x))