Minimum Product (Codeforces 1409B)
Tags: Greedy, brute force

You are given four integers $$$a$$$, $$$b$$$, $$$x$$$ and $$$y$$$. Initially, $$$a \ge x$$$ and $$$b \ge y$$$. You can do the following operation no more than $$$n$$$ times:  Choose either $$$a$$$ or $$$b$$$ and decrease it by one. However, as a result of this operation, value of $$$a$$$ cannot become less than $$$x$$$, and value of $$$b$$$ cannot become less than $$$y$$$. Your task is to find the minimum possible product of $$$a$$$ and $$$b$$$ ($$$a \cdot b$$$) you can achieve by applying the given operation no more than $$$n$$$ times.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The only line of the test case contains five integers $$$a$$$, $$$b$$$, $$$x$$$, $$$y$$$ and $$$n$$$ ($$$1 \le a, b, x, y, n \le 10^9$$$). Additional constraint on the input: $$$a \ge x$$$ and $$$b \ge y$$$ always holds.

Output: For each test case, print one integer: the minimum possible product of $$$a$$$ and $$$b$$$ ($$$a \cdot b$$$) you can achieve by applying the given operation no more than $$$n$$$ times.

Note: In the first test case of the example, you need to decrease $$$b$$$ three times and obtain $$$10 \cdot 7 = 70$$$.In the second test case of the example, you need to decrease $$$a$$$ one time, $$$b$$$ one time and obtain $$$11 \cdot 7 = 77$$$.In the sixth test case of the example, you need to decrease $$$a$$$ five times and obtain $$$5 \cdot 11 = 55$$$.In the seventh test case of the example, you need to decrease $$$b$$$ ten times and obtain $$$10 \cdot 1 = 10$$$.

Sample Inputs:
7
10 10 8 5 3
12 8 8 7 2
12343 43 4543 39 123212
1000000000 1000000000 1 1 1
1000000000 1000000000 1 1 1000000000
10 11 2 1 5
10 11 9 1 10

Sample Outputs:
70
77
177177
999999999000000000
999999999
55
10

Solution (Python):
import math, os, sys
from collections import defaultdict
from fractions import Fraction
from decimal import Decimal
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def solve():
    (a, b, x, y, n) = map(int, input().split())
    p = a - x
    p2 = b - y
    if p + p2 <= n:
        print(x * y)
    else:
        if p >= n:
            prod1 = (a - n) * b
        else:
            q = n - p
            prod1 = x * (b - q)
        if p2 >= n:
            prod2 = a * (b - n)
        else:
            q2 = n - p2
            prod2 = (a - q2) * y
        print(min(prod1, prod2))
for _ in range(int(input())):
    solve()
sys.stdout.close()
sys.stdin.close()

Solution (Python):
m = max
for s in [*open(0)][1:]:
    (a, b, x, y, n) = map(int, s.split())
    c = m(x, a - n)
    d = m(y, b - n)
    print(min(c * m(y, a + b - n - c), d * m(x, a + b - n - d)))

Solution (Python):
m = max
for s in [*open(0)][1:]:
    (a, b, x, y, n) = map(int, s.split())
    c = m(x, a - n)
    d = m(y, b - n)
    print(min(c * m(y, a + b - n - c), d * m(x, a + b - n - d)))