문제 보기 - K개의 묶음 (IZhO14_blocks)

언어	컴파일 명령
C11	/usr/bin/gcc -DEVAL -std=gnu11 -O2 -pipe -static -s -o blocks blocks.c -lm
C++20	/usr/bin/g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o blocks blocks.cpp
C++17	/usr/bin/g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o blocks blocks.cpp
Java	/usr/bin/javac -encoding UTF-8 blocks.java /bin/sh -c echo "Main-Class: blocks" > __manifest__.txt /bin/sh -c jar cfm blocks.jar __manifest__.txt *.class
Pypy 3	/usr/bin/pypy3 -m compileall -b blocks.py /bin/mv blocks.pyc __main__.pyc /usr/bin/zip blocks.pyz.zip __main__.pyc /bin/mv blocks.pyz.zip blocks.pyz

시간 제한	메모리 제한	제출 횟수	제출한 사람 수	해결한 사람 수	정답률
1000 ms	256 MiB	2800	486	368	75.72%

길이가 $N$ 인 수열 $A$ 가 주어집니다. 수열의 "분할 값"을 수열을 $K$ 개의 묶음으로 분할했을 때 각 묶음의 최댓값들의 합으로 정의합시다. (각 묶음은 연속해야 합니다) $K$ 가 주어질 때 최소한의 분할 값을 구하는 프로그램을 작성하세요.

입력 형식

첫 번째 줄에 두 개의 정수 $N$ 과 $K$ 가 주어집니다. 두 번째 줄에 $N$ 개의 정수 $A_{1}, A_{2}, \cdots, A_{N}$ ( $1 \le A_{i} \le 10^{6}$ )가 주어집니다.

최소한의 분할 값을 출력합니다.

5 1
1 2 3 4 5

5 2
1 2 3 4 5

문제 출처