421. k-th Product
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
Consider
n integer numbers
a1,
a2,...,
an. Consider the products of their
m-tuples:
b1,
b2,...,
bN. You are to find
k-th largest product, i.e.,
k-th item in the list (
bi) sorted in non-increasing order (items of the list are numbered starting from 1).
Note that the numbers can be negative.
Input
The input file contains three integer numbers
n,
m,
k (1 ≤
n,
k ≤ 10000, 1 ≤
m ≤ 13,
k ≤
Cnm), followed by
n integer numbers
ai (-10
6 ≤
ai ≤ 10
6).
Output
Output one integer number — the
k-th largest product.
Example(s)
sample input | sample output |
4 3 3
2 3 3 5
|
30
|
There are four possible products in the example: 3 · 3 · 5 = 45, 2 · 3 · 5 = 30 (involving the first 3), 2 · 3 · 5 = 30 (involving the second 3), 2 · 3 · 3 = 18.