Codeforces #350 Div2. D. Magic Powder

F問題みたいの一発で通る気しない。
http://codeforces.com/contest/670/problem/D2

問題

クッキーを１枚作るのに、i種類目の材料がA[i]グラムいる。
今手元には各材料がB[i]グラムずつあるほか、他のあらゆる材料の代替に使える魔法の材料がKグラムある。
魔法の材料を最適に使う場合、クッキーを最大何枚作れるか

解法

クッキーの枚数を定めると必要な魔法の材料の最小グラム数がわかるので、クッキー枚数で二分探索すればよい。
最小グラム数の計算は途中で適度に打ち切らないとオーバーフローするので気を付けよう。

int N,K;
pair<int,int> P[101010];

int ok(ll num) {
	ll left=K;
	int i;
	FOR(i,N) {
		left -= max(0LL,P[i].first*num-P[i].second);
		if(left<0) return 0;
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>P[i].first;
	FOR(i,N) cin>>P[i].second;
	
	ll ret=0;
	for(i=31;i>=0;i--) if(ok(ret+(1LL<<i))) ret+=1LL<<i;
	cout<<ret<<endl;
}

まとめ

こういうオーバーフロー回避は本題と余り関係ないでやめてほしいんだけどな…。