結果
問題 |
No.1012 荷物収集
|
ユーザー |
|
提出日時 | 2020-07-06 17:01:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 244 ms / 2,000 ms |
コード長 | 1,017 bytes |
コンパイル時間 | 1,022 ms |
コンパイル使用メモリ | 80,176 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-24 17:15:11 |
合計ジャッジ時間 | 9,368 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; typedef pair<int,int> pii; typedef long long ll; int main(){ int n, q; cin >> n >> q; vector<pii> vp; for(int i = 0; i < n; i++){ int x, w; cin >> x >> w; vp.push_back({x,w}); } sort(vp.begin(), vp.end()); vector<pii> ev; ev = vp; for(int i = 1; i <= q; i++){ int x; cin >> x; ev.push_back({x, -i}); } sort(ev.begin(), ev.end()); int st = ev[0].first; ll tmp = 0, l = 0, r = 0; for(int i = 0; i < n; i++){ tmp += (ll)(vp[i].first-st)*vp[i].second; r += vp[i].second; } vector<ll> ans(q+1); for(pii p : ev){ int x = p.first, y = p.second; ll diff = x-st; tmp += diff*l - diff*r; if(y < 0){ ans[-y] = tmp; }else{ l += y; r -= y; } st = x; } for(int i = 1; i <= q; i++) cout << ans[i] << endl; return 0; }