[蓝桥杯 2018 省 B] 乘积最大

Luogu
IDLGP8669
Time1000ms
Memory256MB
DifficultyP3
贪心2018蓝桥杯省赛分类讨论
给定 $N$ 个整数 $A_1, A_2,\cdots, A_N$。请你从中选出 $K$ 个数,使其乘积最大。 请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 $1000000009$(即 $10^9+9$)的余数。 注意,如果 $X<0$, 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\bmod 1000000009)$。 ## Input 第一行包含两个整数 $N$ 和 $K$。 以下 $N$ 行每行一个整数 $A_i$。 ## Output 一个整数,表示答案。 [samples] ## Note 对于 $40\%$ 的数据,$1\le K\le N\le 100$。 对于 $60\%$ 的数据,$1\le K \le 1000$。 对于 $100\%$ 的数据,$1\le K\le N\le 10^5$,$-10^5\le A_i\le 10^5$。
Samples
Input #1
5 3 
-100000   
-10000   
2   
100000  
10000
Output #1
999100009
Input #2
5 3 
-100000   
-100000   
-2   
-100000  
-100000
Output #2
-999999829
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2018 省 B] 乘积最大",
    "description": {
      "content": "给定 $N$ 个整数 $A_1, A_2,\\cdots, A_N$。请你从中选出 $K$ 个数,使其乘积最大。   请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 $1000000009$(即 $10^9+9$)的余数。   注意,如果 $X<0$, 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\\bmod 1000000009)$。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8669"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $N$ 个整数 $A_1, A_2,\\cdots, A_N$。请你从中选出 $K$ 个数,使其乘积最大。  \n\n请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 $1000000009$(即 $10^9+9$)的余数。  \n\n注意,如果 $X<0$, 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\\bmod 1000000009)$。\n\n## ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments