X and Two Groups

All submissions for this problem are available.
Read problems statements in Mandarin chinese , Russian and Vietnamese as well.
Tumut, the best programmer in his village Applidz, invented a problem and decided to share it with you: You are given two integer sequences $S_1, S_2, \dots, S_N$ and $T_1, T_2, \dots, T_M$ and an integer $x$. You are allowed to perform the following operation any number of times:  choose an element of $S$ and an element of $T$ (let's denote them by $S_i$ and $T_j$ respectively)  decrease both $S_i$ and $T_j$ by $x$, i.e. replace $S_i$ by $S_ix$ and $T_j$ by $T_jx$ Let's denote the minimum and maximum value in the sequence $S$ after performing the chosen operations (possibly none) by $minS$ and $maxS$ respectively. Similarly, let's denote the minimum and maximum value in $T$ after performing the chosen operations by $minT$ and $maxT$ respectively. The goal is minimizing the expression $(maxS+maxT)  (minS+minT)$. Compute the minimum value of this expression. ### Input  The first line of the input contains three spaceseparated integers $N$, $M$ and $x$.  The second line contains $N$ spaceseparated integers $S_1, S_2 \dots S_N$.  The third line contains $M$ spaceseparated integers $T_1, T_2 \dots T_M$. ### Output Print a single line containing one integer — the minimum possible value of the expression $(maxS+maxT)  (minS+minT)$. ### Constraints  $1 \le N, M \le 5\cdot 10^5$  $1 \le S_i \le 10^9$ for each valid $i$  $1 \le T_i \le 10^9$ for each valid $i$  $1 \le x \le 10^9$ ### Subtasks **Subtask #1 (20 points):**  $N, M \le 20$  $S_i \le 20$ for each valid $i$  $T_i \le 20$ for each valid $i$ **Subtask #2 (30 points):**  $N, M \le 1,000$  $S_i \le 1,000$ for each valid $i$  $T_i \le 1,000$ for each valid $i$ **Subtask #3 (50 points):** original constraints ### Example Input ``` 2 2 3 1 8 2 3 ``` ### Example Output ``` 2 ``` ### Explanation We can perform these two operations: 1. decrease $S_2$ and $T_1$ by $x$ 2. decrease $S_2$ and $T_2$ by $x$ Afterwards, the sequence $S$ will be $[1, 2]$ and the sequence $T$ will be $[1, 0]$. The resulting value of the given expression is $(2+0)(1+(1)) = 2$. It is impossible to obtain a smaller value no matter how many operations are performed.Author:  allllekssssa 
Editorial  https://discuss.codechef.com/problems/XTGR 
Tags  allllekssssa, greedy, ltime63, numbertheory 
Date Added:  24082018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 