USACO 2018 December Gold, Problem 3- 팀워크 > 문제은행 : 정보올림피아드&알고리즘




3382 : 팀워크

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
21 회   
시도횟수
38 회   

문제

 

당신은 여느 때와 다름 없이 눈을 떴다. 여러분들 모두가 군대에 있었다!

당신은 지금부터 1번부터 N번까지 N명의 훈련병들과 함께 사격 연습을 해야 한다. 

각 훈련병들은 모두 다른 사격 기술을 가지고 있다.

이 훈련소의 교관인 택쌤은, 훈련병들을 몇 팀으로 나누어 배치하려고 한다. 

같은 팀에 배치된 훈련병들은, 가장 실력이 좋은 훈련병에게 배우기 때문에 그와 같은 실력이 된다. 

군대 내 질서를 위해, 연속된 번호의 훈련병만이 팀으로 구성될 수 있으며, 팀원들은 한 팀에 최대 K명만 들어갈 수 있다. 

어떤 훈련병은 불가피하게 팀 없이 사격 연습을 할 수도 있다.

교관 택쌤은 부대 내 훈련병들의 사격 실력의 합이 최대가 되도록 하고 싶다. 

팀 구성 후의 사격 실력 합의 최댓값을 구하는 프로그램을 작성하라.

 

[입력 예 설명]

[1 15
7] 9 [2 5 10]
으로 묶는 것이
최댓값이다.


입력형식

첫 줄에 N(1<=N<=10,000)과 K(1<=K<=1,000)가 주어진다. 다음 N줄에 걸쳐, 각 훈련병들의 사격 실력이 주어진다.(최대 100,000)

출력형식

팀 구성 후, 가능한 사격 실력 합의 최댓값을 출력한다.

입력 예

7 3
1
15
7
9
2
5
10

출력 예

84


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP