結果
問題 |
No.1012 荷物収集
|
ユーザー |
|
提出日時 | 2020-03-29 14:58:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 276 ms / 2,000 ms |
コード長 | 1,720 bytes |
コンパイル時間 | 1,735 ms |
コンパイル使用メモリ | 170,244 KB |
実行使用メモリ | 7,936 KB |
最終ジャッジ日時 | 2025-01-02 13:27:12 |
合計ジャッジ時間 | 11,533 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; typedef long long ll; typedef pair<ll,ll> P; const ll INF = 1e18; const int MOD = 1000000007; int main() { int n,q; cin >> n >> q; vector<P> carry(n); rep(i,n) cin >> carry[i].first >> carry[i].second ; sort(carry.begin(),carry.end()); vector<ll> left(n),right(n),left_w(n),right_w(n); ll now = 0; rep(i,n){ if(i == 0){ left[0] = 0; now += carry[i].second; } else{ left[i] = left[i-1] + (carry[i].first - carry[i-1].first) * now; now += carry[i].second; } left_w[i] = now; } now = 0; for(int i=n-1;i>=0;i--){ if(i == n-1){ right[i] = 0; now += carry[i].second; } else{ right[i] = right[i+1] + (carry[i+1].first - carry[i].first) * now; now += carry[i].second; } right_w[i] = now; } auto ok = [&](int i,ll j){ if(i == n) return true; if(i == -1) return false; return carry[i].first >= j; }; rep(i,q){ ll x; cin >> x; int l = -1,r = n; while(r - l > 1){ int m = (l + r)/2; if(ok(m,x)) r = m; else l = m; } ll res; if(r == n){ res = left[n-1] + left_w[n-1] * (x - carry[n-1].first); } else if(l == -1){ res = right[0] + right_w[0] * (carry[0].first - x); } else{ res = left[l] + right[r] + left_w[l]*(x-carry[l].first) + right_w[r]*(carry[r].first-x); } cout << res << endl; } return 0; }