[Codeforces] Codeforces Round #667 (Div. 3) B. Minimum Product

2020年12月13日

問題

方針

自然数 \( 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;
}