#382810 (C++14) No.885 アマリクエリ

• 問題: No.885 アマリクエリ
• ユーザー: otera
• 提出日時: 2019-09-24 06:47:58
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 300 ms / 2,000 ms
• コード長: 1,975 bytes
• コンパイル時間: 970 ms
• コンパイル使用メモリ: 119,980 KB
• 実行使用メモリ: 9,728 KB
• 最終ジャッジ日時: 2024-09-19 04:57:10
• 合計ジャッジ時間: 3,817 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	131 ms; 5,248 KB
testcase_01	AC	279 ms; 9,728 KB
testcase_02	AC	190 ms; 9,728 KB
testcase_03	AC	134 ms; 5,376 KB
testcase_04	AC	144 ms; 5,376 KB
testcase_05	AC	136 ms; 5,376 KB
testcase_06	AC	125 ms; 5,376 KB
testcase_07	AC	33 ms; 9,600 KB
testcase_08	AC	123 ms; 5,376 KB
testcase_09	AC	300 ms; 9,728 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	4 ms; 5,376 KB
testcase_14	AC	4 ms; 5,376 KB
testcase_15	AC	4 ms; 5,376 KB
testcase_16	AC	3 ms; 5,376 KB
testcase_17	AC	3 ms; 5,376 KB
testcase_18	AC	3 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	3 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB

ソースコード

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define int long long

//P mod Q ( Q < P )は P / 2 未満

void solve() {
	int n, q; cin >> n;
    map<int, int> m;
    int sum = 0;
    rep(i, n) {
        int x; cin >> x;
        m[x] ++; sum += x;
    }
    cin >> q;
    while(q--) {
        int x; cin >> x;
        while(m.rbegin()->first >= x) {
            int nx = m.rbegin()->first;
            int ny = m.rbegin()->second;
            sum -= (nx - nx % x) * ny;
            m.erase(nx);
            m[nx % x] += ny;
        }
        cout << sum << endl;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}