RiseOJ – 베리 따기

설명

베시와 여동생 엘시는 농부 존의 베리 밭에서 베리를 따고 있다. 농부 존의 밭에는 정확히 $$N$$ 그루의 베리 나무( $1\le N\le 1000$ )가 있으며, 나무 $$i$$ 에는 정확히 $$B_i$$ 개의 베리( $1\le B_i\le 1000$ )가 달려 있다. 베시에게는 정확히 $$K$$ 개의 바구니( $1 \le K \le 1000$ , $$K$$ 는 짝수)가 있다. 각 바구니에는 한 나무에서 딴 베리를 원하는 만큼 담을 수 있지만, 서로 다른 두 나무의 베리를 함께 담을 수는 없다. 맛이 서로 충돌하기 때문이다. 바구니는 비어 있어도 된다.

베시는 자신이 모으는 베리의 개수를 최대화하고 싶다. 하지만 농부 존은 베시가 여동생과 나누기를 바라므로, 베시는 베리가 가장 많이 담긴 $$K/2$$ 개의 바구니를 엘시에게 주어야 한다. 이 때문에 엘시가 베시보다 더 많은 베리를 갖게 될 수도 있는데, 이는 매우 불공평하지만, 안타깝게도 남매 사이가 항상 공평한 것은 아니다.

베시가 모을 수 있는 베리의 최대 개수를 구하도록 도와주자.

문제 제공: Nathan Pinsker

제약

점수 배점

테스트 케이스 1-4는 $K\le 10$ 을 만족한다.
테스트 케이스 5-11은 추가 제약이 없다.

문제 제공: Nathan Pinsker

입력 형식

첫째 줄에 공백으로 구분된 정수 $$N$$ 과 $$K$$ 가 주어진다.

둘째 줄에 공백으로 구분된 $$N$$ 개의 정수 $B_1,B_2,\ldots,B_N$ 이 주어진다.

출력 형식

답을 한 줄에 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 berries.in · 출력을 쓸 파일 berries.out

예제 1

입력

5 4
3 6 8 4 2

출력

설명

If Bessie fills

one basket with 6 berries from tree 2
two baskets, each with 4 berries from tree 3
one basket with 4 berries from tree 4

then she receives two baskets each with 4 berries, giving her 8 berries in
total.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > January > Silver

올림피아드 > USACO > 2019-2020 > January > Silver

태그

JudgeUSACO

베리 따기

평가 및 의견

풀이 제출