結果
問題 | No.885 アマリクエリ |
ユーザー |
![]() |
提出日時 | 2019-09-13 23:10:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 1,191 bytes |
コンパイル時間 | 1,588 ms |
コンパイル使用メモリ | 173,316 KB |
実行使用メモリ | 5,604 KB |
最終ジャッジ日時 | 2024-07-04 10:23:56 |
合計ジャッジ時間 | 3,759 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; #define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0) #define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0) int main() { int n,q; cin >> n; vector<int> a(n); for (int i = 0;i < n;++i) cin >> a[i]; cin >> q; vector<ll> ans(q,0); vector<P> b; int mx = INT_MAX; for (int i = 0;i < q;++i) { int x; cin >> x; if (x < mx) { b.push_back(P(-x,i)); mx = x; } } for (int i = 0;i < n;++i) { ans[0] += a[i]; while (1) { int j = lower_bound(b.begin(),b.end(),P(-a[i],0))-b.begin(); if (j == b.size()) break; ans[b[j].second] -= a[i]/(-b[j].first)*(-b[j].first); a[i] %= -b[j].first; } } for (int i = 1;i < q;++i) ans[i] += ans[i-1]; for (int i = 0;i < q;++i) cout << ans[i] << "\n"; }