結果
問題 |
No.1012 荷物収集
|
ユーザー |
![]() |
提出日時 | 2020-03-21 09:53:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 828 bytes |
コンパイル時間 | 871 ms |
コンパイル使用メモリ | 78,520 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-12-17 23:15:37 |
合計ジャッジ時間 | 5,611 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; using P = pair<ll, ll>; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; vector<P> xw(N); for (int i = 0; i < N; i++) { ll x, w; cin >> x >> w; xw[i] = P(x, w); } sort(xw.begin(), xw.end()); vector<ll> csXW(N+1), csW(N+1); for (int i = 0; i < N; i++) { csXW[i+1] = csXW[i] + xw[i].first * xw[i].second; csW[i+1] = csW[i] + xw[i].second; } for (int i = 0; i < Q; i++) { ll X; cin >> X; int k = lower_bound(xw.begin(), xw.end(), P(X, 0)) - xw.begin(); ll ans = 0; ans += csXW.back() - 2 * csXW[k]; ans += 2 * X * csW[k] - X * csW.back(); cout << ans << "\n"; } }