Submission #1687117

---

Source Code Expand

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;

#define INF 2147483647
#define LINF 9223372036854775807
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<ll, int> P;

int n;
ll cnta[100000],cntb[100000];
ll a,b,sum;
priority_queue<P> pq;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin>>n>>a>>b;
	REP(i,n) {
		ll h; cin>>h;
		pq.push(P(h,i));
	}
	while (!pq.empty()) {
		cout<<sum<<endl;
		P p=pq.top(); pq.pop();
		ll h=p.first;
		int idx=p.second;
		h-=(sum-cnta[idx]-cntb[idx])*b;
		//cout<<"1h,idx,sum,cnta,cntb "<<h<<' '<<idx<<' '<<sum<<' '<<cnta[idx]<<' '<<cntb[idx]<<endl;
		cntb[idx]=sum-cnta[idx];
		if(h<=0) continue;
		sum++,h-=a,cnta[idx]++;
		//cout<<"2h,idx,sum,cnta,cntb "<<h<<' '<<idx<<' '<<sum<<' '<<cnta[idx]<<' '<<cntb[idx]<<endl;
		if(h<=0) continue;
		pq.push(P(h,idx));
	}
	cout<<sum<<endl;

	return 0;
}

Submission Info

Judge Result