提出 #58511372

---

ソースコード 拡げる

// E - Sensor Optimization Dilemma 2
#include<bits/stdc++.h>
#define ceil(x, y) ((x) / (y) + !!((x) % (y)))

using namespace std;

typedef long long i64;

int main()
{
	int n, lim;
	cin >> n >> lim;
	vector<i64> A(n), B(n), P(n), Q(n);
	for(int i = 0; i < n; i++)
		cin >> A[i] >> P[i] >> B[i] >> Q[i];
		
	auto check = [&](const i64 x) -> bool
	{
		i64 tot = 0;
		for(int i = 0; i < n; i++)
		{
			i64 a = A[i], b = B[i], p = P[i], q = Q[i], xx = x, add = 0x3f3f3f3f3f3f3f3f;
			
			for(int j = 0; j < b; j++)
			{
				i64 tmp = j * p + ceil(max(0ll, xx - j * a), b) * q;
				add = min(add, tmp);
			}
			for(int j = 0; j < a; j++)
			{
				i64 tmp = j * q + ceil(max(0ll, xx - j * b), a) * p;
				add = min(add, tmp);
			}
			
			tot += add;
			if(tot > lim) return false;
		}
		return true;
	};
	
	int L = 0, R = 1e9, ans = -1;
	while(L <= R)
	{
		int mid = (L + R) >> 1;
		if(check(mid)) L = mid + 1, ans = mid;
		else R = mid - 1;
	}
	
	cout << ans << endl;
	
	return 0;
}

提出情報

ジャッジ結果