結果
問題 |
No.1012 荷物収集
|
ユーザー |
![]() |
提出日時 | 2020-04-08 23:16:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 968 bytes |
コンパイル時間 | 3,837 ms |
コンパイル使用メモリ | 205,332 KB |
最終ジャッジ日時 | 2025-01-09 15:13:19 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include<bits/stdc++.h> #define ALL(v) std::begin(v),std::end(v) using lint=long long; using ld=long double; int main(){ std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false); std::cout.setf(std::ios_base::fixed);std::cout.precision(15); lint n,q;std::cin>>n>>q; std::vector<std::pair<lint,lint>>xw(n); for(auto&&p:xw)std::cin>>p.first>>p.second; xw.emplace_back(1'000'000'000,0); n++; std::sort(ALL(xw)); std::vector<lint>x(n),w(n+1),dp(n); for(lint i=0;i<n;i++){ std::tie(x.at(i),w.at(i+1))=xw.at(i); } std::partial_sum(ALL(w),w.begin()); for(lint i=1;i<n;i++){ dp.at(0)+=(x.at(i)-x.at(0))*(w.at(i+1)-w.at(i)); } for(lint i=1;i<n;i++){ dp.at(i)+=dp.at(i-1)+(2*w.at(i)-w.at(n))*(x.at(i)-x.at(i-1)); } while(q--){ lint X;std::cin>>X; lint i=std::lower_bound(ALL(x),X)-x.begin(); std::cout<<dp.at(i)+(w.at(n)-2*w.at(i))*(x.at(i)-X)<<'\n'; } }