[Codeforces] Codeforces Round #667 (Div. 3) B. Minimum Product
問題
方針
自然数 \( t, u \ (t \leq u)\) とし、\( f(t, u) = tu \) を考えます。
\[ f(t – 1, u) \leq f(t, u – 1)\]
が成り立つので、\( t \) を減少させた方が \( f(t, u) \) が小さくなることが分かります。\( t, u \) に制約がなければ、\( t \) を減少させた方が最適ですが、 \( x \leq a \wedge y \leq b\) という制約があるので、
\[ \max(x, a – n) \leq \max(y, b – n)\]
であるとき、先に \( a \) を可能な限り減少させてから \( b \) を減少させます。そうではないときは、\( b \) を先に減少させます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll solve(ll a, ll b, ll x, ll y, ll n) { if (max(x, a - n) < max(y, b - n)) { ll ca = max(x, a - n); n -= a - ca; ll cb = max(y, b - n); return ca * cb; } else { ll cb = max(y, b - n); n -= b - cb; ll ca = max(x, a - n); return ca * cb; } } int main() { int t; cin >> t; ll a, b, x, y, n; ll ans[t]; for (int i = 0; i < t; i++) { cin >> a >> b >> x >> y >> n; ans[i] = solve(a, b, x, y, n); } for (ll i : ans) { cout << i << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません