给定 N个整数 A1,A2,…AN。
请你从中选出 K个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009的余数。
注意，如果 X<0， 我们定义 X 除以 1000000009的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)
输入格式
第一行包含两个整数 N 和 K。
以下 N行每行一个整数 Ai。
输出格式
输出一个整数，表示答案。
数据范围
1≤K≤N≤10
−105≤Ai≤10
输入样例1：
5 3 -100000-10000 2 100000 10000
输出样例1：
999100009
输入样例2：
5 3 -100000-100000-2-100000-100000
输出样例2：
-999999829
#include<iostream> #include<algorithm> using namespace std; const int N = 100010, mod = 1000000009; typedef long long ll; int n, k; int a[N]; int main() { cin >> n >> k; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); int res = 1, sign = 1; int l = 0, r = n - 1; if (k % 2) { res = a[r--]; k--; if (res < 0) sign = -1; } while (k) { ll x = (ll)a[l] * a[l + 1], y = (ll)a[r - 1] * a[r]; if (x * sign > y * sign) { res = x % mod * res % mod; l += 2; } else { res= y % mod * res % mod; r -= 2; } k -= 2; } cout << res << endl; return 0; }
