結果

問題 No.1012 荷物収集
ユーザー lam6er
提出日時 2025-03-20 20:20:35
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,038 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 125,668 KB
最終ジャッジ日時 2025-03-20 20:21:30
合計ジャッジ時間 11,211 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    q = int(input[ptr])
    ptr += 1
    
    goods = []
    for _ in range(n):
        x = int(input[ptr])
        ptr += 1
        w = int(input[ptr])
        ptr += 1
        goods.append((x, w))
    
    goods.sort()
    xs = [x for x, w in goods]
    ws = [w for x, w in goods]
    
    sum_w = [0] * (n + 1)
    sum_xw = [0] * (n + 1)
    for i in range(n):
        sum_w[i+1] = sum_w[i] + ws[i]
        sum_xw[i+1] = sum_xw[i] + xs[i] * ws[i]
    
    x_queries = list(map(int, input[ptr:ptr+q]))
    ptr += q
    
    results = []
    for X in x_queries:
        k = bisect.bisect_left(xs, X)
        left_w = sum_w[k]
        left_xw = sum_xw[k]
        right_w = sum_w[n] - left_w
        right_xw = sum_xw[n] - left_xw
        cost = X * left_w - left_xw + right_xw - X * right_w
        results.append(cost)
    
    print('\n'.join(map(str, results)) + '\n')

if __name__ == '__main__':
    main()
0