标题：乘积最大
给定N个整数A1, A2, ... AN。请你从中选出K个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。
注意，如果X<0， 我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。
即：0-((0-x) % 1000000009)
【输入格式】
第一行包含两个整数N和K。
以下N行每行一个整数Ai。
对于40%的数据，1 <= K <= N <= 100
对于60%的数据，1 <= K <= 1000
对于100%的数据，1 <= K <= N <= 100000 -100000 <= Ai <= 100000
【输出格式】
一个整数，表示答案。
【输入样例】
5 3
-100000
-10000
2
100000
10000
【输出样例】
999100009
再例如：
【输入样例】
5 3
-100000
-100000
-2
-100000
-100000
【输出样例】
-999999829
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
using namespace std;
typedef long long LL;
const int maxn=100000+50;
const int mod=1e9+9;
/**
先把0给排除出去 不然*0直接变为0了
分为几种情况
全为正数 则直接选取最大的K个
全为负数 若K为偶数 选最大的K个 若K为奇数 选K个最小的
既有正数又有负数 前K个中有偶数个负数直接选前K个
若前K个有奇数个负数的话 这就要仔细想一下了
把最小的负数和K个数之后最大的正数交换一下是一种情况
把最小的正数和K个数最大的负数交换一下也是一种情况
可能有人会说了 如果换不了怎么办？ 是的 的确存在这种情况 换不了的话 证明结果就是负数（当然有0的话就是0）
*/
LL N,K;
struct Node
{
LL v,p;
};
bool cmp(const Node a,const Node b)
{
return a.v>b.v;
}
Node a[maxn];
LL solve(LL n)
{
LL sum=1,cnt1=0;
if(n==0)//从后往前选K个
{
for(int i=N-1;i>=N-K;i--)
{
sum=sum*a[i].v%mod;
if(a[i].p==1) cnt1++;
}
}
else //从前往后
{
for(int i=0;i<K;i++)
{
sum=sum*a[i].v%mod;
if(a[i].p==1) cnt1++;
}
}
if(cnt1%2==1)//奇数个
return -sum;
else return sum;
}
int main()
{
cin>>N>>K;
LL cnt1=0,cnt2=0;//正数和负数个数
LL flag=0;//是否有0
LL ans=-1;
for(int i=0;i<N;i++)//去掉0后 绝对值放在数组中
{
cin>>a[i].v;
if(a[i].v<0)
{
a[i].p=1;//表示负数
a[i].v=-a[i].v;
cnt2++;
}
else if(a[i].v>0)
{
a[i].p=0;//表示正数
cnt1++;
//a[i].v=-a[i].v;
}
else
{
flag=1;
i--;
N--;
}
}
sort(a,a+N,cmp);
// for(int i=0;i<N;i++)
// {
// if(a[i].p==1) cnt1++;
// else cnt2++;
// }
if(N<K) ans=0;//一定要选0 所以答案就只有0 了
else if(cnt2==N)// 全为负数
{
if(K%2==1)//从后往前选K个数才会使得答案最小
ans=solve(0);
else ans=solve(1);//从前往后
}
else if(cnt1==N)//全为正数
{
ans=solve(1);
}
else//有正有负
{
LL p1=-1,p2=-1;
for(int i=K-1;i>=0;i--)//找最小的负数
{
if(a[i].p==1)
{
p1=i;
break;
}
}
for(int i=K;i<N;i++)//K个数之后最小的大的正数
{
if(a[i].p==0)
{
p2=i;
break;
}
}
if(p1!=-1&&p2!=-1)//最小的负数换最大的正数
{
LL sum=1;
swap(a[p1],a[p2]);
for(int i=0;i<K;i++) sum=sum*a[i].v%mod;
swap(a[p1],a[p2]);
ans=sum;
}
p1=-1,p2=-1;
for(int i=K-1;i>=0;i--)
{
if(a[i].p==0)//最小的正数
{
p1=i;
break;
}
}
for(int i=K;i<N;i++)//最大的负数
{
if(a[i].p==1)
{
p2=i;
break;
}
}
if(p1!=-1&&p2!=-1)//最小的正数换最大的负数
{
LL sum=1;
swap(a[p1],a[p2]);
for(int i=0;i<K;i++) sum=sum*a[i].v%mod;
swap(a[p1],a[p2]);
ans=max(ans,sum);
}
if(ans<-1)
{
solve(0);
}
}
if(ans<0&&flag) ans=0;
cout<<ans<<endl;
return 0;
}