시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 699 | 63 | 58 | 12.747% |
동현이는 성냥팔이 소년이다. 하지만, 요즘 같은 세상에 성냥을 사는 사람이 어디 있겠는가. 안 팔리는 성냥만 집에 잔뜩 쌓인 동현이는 성냥개비를 가지고 뭐라도 하고 놀려고 한다.
동현이는 지금 정수 N개와 성냥개비 K개를 가지고 있다. 우선, 동현이는 T라는 정수를 하나 만들고 그 값을 1로 정했다. 이후, 동현이는 N개의 정수 각각에 대해서 다음 세 가지 행동 중 하나를 할 것이다.
각 정수에 대해 할 수 있는 3가지 행동.
동현이는 성냥개비를 원하는 만큼 사용하여 T의 값을 최대화하고 싶다. (성냥개비를 사용하지 않아도 된다.) 하지만 동현이는 몇 번 해보다가 싫증이 나서 던져버리고 게임이나 하러 가 버렸다. 여러분은 똑똑하니까 동현이 대신 이 문제를 풀어 주자!
첫 줄에 동현이가 가진 정수의 개수 N과 성냥개비의 개수 K가 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ K ≤ 2×N)
두 번째 줄에 동현이가 가진 N개의 정수들이 주어진다. 각 수들의 절댓값은 109 이하이다.
동현이가 성냥개비를 적절히 사용하여 T의 값을 최대화했을 때, 그 값을 109+7로 나눈 나머지를 출력한다.
5 3 2 3 -4 -5 6
90
동현이가 3, -5, 6에 각각 성냥개비 1개씩을 썼을 때 T의 값이 (-3) × 5 × (-6) = 90으로 최대이다.
University > 서울대학교 > 2019 서울대학교 프로그래밍 경시대회 > Division 1 C번
University > 서울대학교 > 2019 서울대학교 프로그래밍 경시대회 > Division 2 H번