| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 200 | 64 | 55 | 41.353% |
You are given a sequence A of N positive integers. Let’s define “value of a splitting” the sequence to K blocks as a sum of maximums in each of K blocks. For given K find the minimal possible value of splittings.
First line of the input file contains two integers N and K. Next line contains N integers A1, A2, . . . , AN (1 ≤ Ai ≤ 106) — the sequence elements.
Output one number — minimal possible value of a splittings.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 14 | 1 ≤ N ≤ 100, 1 ≤ K ≤ min(N, 5) |
| 2 | 18 | 1 ≤ N ≤ 20, 1 ≤ K ≤ min(N, 20) |
| 3 | 21 | 1 ≤ N ≤ 100, 1 ≤ K ≤ min(N, 100) |
| 4 | 47 | 1 ≤ N ≤ 100000, 1 ≤ K ≤ min(N, 100) |
5 1 1 2 3 4 5
5
5 2 1 2 3 4 5
6
Olympiad > International Zhautykov Olympiad > IZhO 2014 E번