結果

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

ソースコード

diff # 

import bisect
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    Q = int(data[idx+1])
    idx +=2
    xw = []
    for _ in range(N):
        x = int(data[idx])
        w = int(data[idx+1])
        xw.append((x, w))
        idx +=2
    xw.sort()
    x_sorted = [x for x, w in xw]
    w_sorted = [w for x, w in xw]
    
    # Compute prefix sums
    prefix_weights = [0] * (N+1)
    prefix_wx = [0] * (N+1)
    for i in range(1, N+1):
        prefix_weights[i] = prefix_weights[i-1] + w_sorted[i-1]
        prefix_wx[i] = prefix_wx[i-1] + w_sorted[i-1] * x_sorted[i-1]
    
    total_weights = prefix_weights[N]
    total_wx = prefix_wx[N]
    
    # Process queries
    X_list = list(map(int, data[idx:idx+Q]))
    for X in X_list:
        k = bisect.bisect_right(x_sorted, X)
        sum_left_weights = prefix_weights[k]
        sum_left_wx = prefix_wx[k]
        sum_right_weights = total_weights - sum_left_weights
        sum_right_wx = total_wx - sum_left_wx
        cost = (X * sum_left_weights - sum_left_wx) + (sum_right_wx - X * sum_right_weights)
        print(cost)
    
if __name__ == '__main__':
    main()
0