레이팅 미적용농부 존은 가장 좋아하는 명절을 맞아 친구들에게 선물을 보내고 싶어한다. 그는 선물 포장을 잘하지 못하기 때문에 소들의 도움을 받으려 한다. 예상할 수 있듯이 소들도 선물 포장을 그다지 잘하지는 못하는데, 농부 존은 이 교훈을 곧 뼈저리게 배우게 될 것이다.
농부 존의 \(N\)마리 소 (\(1 \leq N \leq 10^4\))는 모두 한 줄로 서 있으며, 편의상 순서대로 \(1 \ldots N\)번으로 번호가 매겨져 있다. 소 \(i\)의 선물 포장 실력은 \(s_i\)이다. 실력 수준이 꽤 다를 수 있으므로, 농부 존은 소들을 팀으로 묶기로 한다. 하나의 팀은 연속한 최대 \(K\)마리 (\(1 \leq K \leq 10^3\))의 소로 구성될 수 있으며, 어떤 소도 둘 이상의 팀에 속할 수 없다. 소들은 서로에게서 배우기 때문에, 팀에 속한 각 소의 실력은 그 팀에서 실력이 가장 뛰어난 소의 실력으로 대체될 수 있다.
팀을 최적으로 구성했을 때 농부 존이 얻을 수 있는 실력의 합의 최댓값을 구하도록 도와주자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)과 \(K\)가 주어진다. 다음 \(N\)개의 줄에 \(N\)마리 소의 실력이 서 있는 순서대로 주어진다. 각 실력 수치는 \(10^5\) 이하의 양의 정수이다.
적절한 연속 구간의 소들을 팀으로 묶어 농부 존이 얻을 수 있는 실력 합의 최댓값을 출력한다.
teamwork.in · 출력을 쓸 파일 teamwork.out7 3
1
15
7
9
2
5
1084In this example, the optimal solution is to group the first three cows and the
last three cows, leaving the middle cow on a team by itself (remember that it is
fine to have teams of size less than \(K\)). This effectively boosts the skill
levels of the 7 cows to 15, 15, 15, 9, 10, 10, 10, which sums to 84.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > December > Gold