codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1409B.md (1911B)


      1 Source: https://codeforces.com/problemset/problem/1409/B
      2 
      3 B. Minimum Product
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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:
     22 
     23 * 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$.
     24 
     25 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.
     26 
     27 You have to answer $t$ independent test cases.
     28 
     29 Input
     30 
     31 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.
     32 
     33 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.
     34 
     35 Output
     36 
     37 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.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 7
     45 10 10 8 5 3
     46 12 8 8 7 2
     47 12343 43 4543 39 123212
     48 1000000000 1000000000 1 1 1
     49 1000000000 1000000000 1 1 1000000000
     50 10 11 2 1 5
     51 10 11 9 1 10
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 70
     58 77
     59 177177
     60 999999999000000000
     61 999999999
     62 55
     63 10
     64 ```
     65 
     66 Note
     67 
     68 In the first test case of the example, you need to decrease $b$ three times and obtain $10 \cdot 7 = 70$.
     69 
     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$.
     71 
     72 In the sixth test case of the example, you need to decrease $a$ five times and obtain $5 \cdot 11 = 55$.
     73 
     74 In the seventh test case of the example, you need to decrease $b$ ten times and obtain $10 \cdot 1 = 10$.