結果

問題 No.1012 荷物収集
ユーザー betrue12
提出日時 2020-03-20 21:41:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 272 ms / 2,000 ms
コード長 738 bytes
コンパイル時間 2,333 ms
コンパイル使用メモリ 203,336 KB
最終ジャッジ日時 2025-01-09 08:26:04
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, Q;
    cin >> N >> Q;
    vector<pair<int64_t, int64_t>> AW(N);
    for(int i=0; i<N; i++){
        int64_t a, w;
        cin >> a >> w;
        AW[i] = {a, w};
    }
    sort(AW.begin(), AW.end());
    vector<int64_t> WS(N+1), AWS(N+1);
    for(int i=0; i<N; i++){
        WS[i+1] = WS[i] + AW[i].second;
        AWS[i+1] = AWS[i] + AW[i].first * AW[i].second;
    }

    while(Q--){
        int64_t X;
        cin >> X;
        int pt = lower_bound(AW.begin(), AW.end(), make_pair(X, int64_t(-1))) - AW.begin();
        int64_t s1 = X*WS[pt] - AWS[pt];
        int64_t s2 = (AWS[N] - AWS[pt]) - X*(WS[N]-WS[pt]);
        cout << s1+s2 << endl;
    }
    return 0;
}
0