Codeforces 371(#218 Div2 only) C. Hamburgers

問題

ハンバーガー一個を作るにはSがrs個, Bがrb個, Cがrc個必要である。
最初Sをns個、Bをnb個、Cをnc個持っている。

足りない材料はSを一個ps円、Bを一個pb円、Cを一個pc円で買えるが、
予算はr円。

最大でハンバーガーはいくつ作れるか求めよ。

制約条件

r≦10^12とか

方針

ハンバーガーを作る個数に関して二分探索すればいい。
個数を決めたら、足りない材料の個数がそれぞれわかるので、
予算に収まるかを調べる。

ソースコード

string s;
int nb, ns, nc, pb, ps, pc;
ll r;

int main(){
	cin >> s;
	cin >> nb >> ns >> nc;
	cin >> pb >> ps >> pc >> r;
	
	int rb = 0, rs = 0, rc = 0;
	
	rep(i, s.size()){
		if(s[i] == 'B') rb++;
		if(s[i] == 'S') rs++;
		if(s[i] == 'C') rc++;
	}
	
	ll lo = 0, hi = 1e15, mid;
	
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		
		ll cost = 0;
		cost += max(0ll, rb * mid - nb) * pb;
		cost += max(0ll, rs * mid - ns) * ps;
		cost += max(0ll, rc * mid - nc) * pc;
		
		if(cost <= r) lo = mid;
		else hi = mid;
	}
	cout << lo << endl;
	
	return 0;
}