The Little Match Girl
Time limit1sMemory limit1024 MB
Choose for each of N integers to skip it, multiply by its negative for 1 matchstick, or multiply by its positive value for 2 matchsticks, spending at most K, to maximize the product modulo 1e9+7.
- Level
Hard8 of 10
- Topics
- Greedy, Sorting, Math, Dynamic programming
- Solved
- No attempts yet
Problem
Donghyun is a matchstick salesman. But who buys matchsticks these days? Stuck at home with piles of unsold matches, he decides to do something, anything, with the matchsticks.
Donghyun currently has N integers and K matchsticks. First he makes an integer T and sets its value to 1. Then for each of the N integers he performs one of the following three actions.
- Skip it without using a matchstick.
- Use 1 matchstick and multiply T by -X, where X is the original value of that integer.
- Use 2 matchsticks and multiply T by +X, where X is the original value of that integer.
The three actions available for each integer.
Donghyun wants to use as many matchsticks as he likes to maximize the value of T. (He does not have to use any.) But after trying a few times he gets bored, throws it all away, and goes off to play games. You are smart, so solve this problem for him!
Input
The first line gives N, the number of integers Donghyun has, and K, the number of matchsticks. (1 ≤ N ≤ 300,000, 1 ≤ K ≤ 2×N)
The second line gives the N integers Donghyun has. The absolute value of each is at most 109.
Output
Print the remainder when the maximum value of T that Donghyun can obtain by using the matchsticks appropriately is divided by 109+7.
Hint
When Donghyun uses 1 matchstick each on 3, -5, and 6, the value of T is (-3) × 5 × (-6) = 90, which is the maximum.