P8669 [Lanqiao Cup 2018 NOI Qualifier B] Maximum Product

Given $N$ integers $A_1, A_2,\cdots, A_N$. Please choose $K$ numbers from them so that their product is maximized. Output the maximum product. Since the product may exceed the integer range, you only need to output the remainder of the product modulo $1000000009$ (i.e., $10^9+9$). Note that if $X

The first line contains two integers $N$ and $K$. In the next $N$ lines, each line contains one integer $A_i$.

Output one integer, the answer.

For $40\%$ of the testdata, $1\le K\le N\le 100$. For $60\%$ of the testdata, $1\le K \le 1000$. For $100\%$ of the testdata, $1\le K\le N\le 10^5$, $-10^5\le A_i\le 10^5$. Translated by ChatGPT 5