C++ 代码

#include<bits/stdc++.h> 
using namespace std;

const int N = 100010, mod = 1000000009;
long long a[N];

int main()
{
    int n,k,l,r,sign = 1;
    long long res = 1;
    cin >> n >> k;
    for(int i=0;i<n;i++)
        cin >> a[i];

    sort(a, a+n);
    l = 0;
    r = n - 1;
    //如果是奇数个
    if(k%2)
    {
        res = a[r];
        r--;
        k--;

        if(res < 0)
            sign = -1;
    } 

    while(k)
    {
        long long x = a[l]*a[l+1];
        long long y = a[r]*a[r-1];
        if(x*sign > y*sign)
        {
            res = x % mod * res % mod;
            l += 2;
        }
        else
        {
            res = y % mod * res % mod;
            r -=2;  
        }
        k -= 2;
    }
    cout << res;
    return 0;
}