| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 246 | 96 | 87 | 45.550% |
좌우로 무한히 긴 수직선 위에 $N$개의 아이템이 떨어져 있다. $i$번째 아이템의 위치는 $i$이며, $A_i$의 가치를 가지고 있다.
주원이에겐 길이가 $K$인 집게가 있는데, 이 집게를 이용하면 주원이가 지정한 정수 좌표 $x(-10^9\le x\le 10^9)$를 기준으로 $x$부터 $x+K-1$까지의 범위에 있는 아이템을 모두 줍는다. 주운 아이템은 그 자리에서 사라지며 주운 아이템은 다시 내려놓을 수 없다. 주원이는 집게를 원하는 만큼 사용해 주운 아이템의 가치의 합이 최대가 되도록 만들고 싶다.
주원이가 주운 아이템 가치의 합으로 가능한 값 중 최댓값을 찾아보자. 집게를 한 번도 사용하지 않을 수도 있으며, 이때 주운 아이템의 총 가치는 0임에 유의하라.
첫째 줄에 아이템의 개수 $N$와 집게의 길이 $K$가 주어진다.
둘째 줄에 아이템의 가치 $A_1,A_2,\cdots ,A_N$이 차례대로 공백으로 구분되어 주어진다.
주운 아이템 가치의 합으로 가능한 값 중 최댓값을 출력한다.
9 3 -2 3 -1 5 4 0 -10 5 -5
11
5 5 1 -10 -10 -10 1
2
$x=-3$과 $x=5$에서 한 번씩 집게를 사용하면 주운 아이템의 가치의 합을 2로 만들 수 있다.
정답이 32비트 정수 범위를 벗어날 수 있으므로 C/C++에서는 long long 타입, Java에서는 long 타입을 사용하는 것을 권장한다.