레이팅 미적용설명
JOI 君の部屋への来客の情報と,JOI 君の持っているマッチの本数が与えられたとき,ストーブがついて
いる時間の合計の最小値を求めよ.
제약
小課題1 [20 点]
以下の条件を満たす.
• N ≦20.
• 1 ≦Ti ≦20 (1 ≦i ≦N).
小課題2 [30 点]
• N ≦5000 を満たす.
小課題3 [50 点]
• 追加の制限はない.
第17 回日本情報オリンピック(JOI 2017/2018) 本選
2018 年2 月11 日(茨城県つくば市)
입력 형식
標準入力から以下の入力を読み込め.
• 1 行目には,2 つの整数N, K が空白を区切りとして書かれている.これは,JOI 君の部屋にN 人の
来客があり,JOI 君はK 本のマッチを持っていることを表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ti が書かれている.これは,i 番目の来客が時刻Ti
に到着し,時刻Ti + 1 に退出することを表す.
출력 형식
標準出力に,ストーブがついている時間の合計の最小値を1 行で出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦100 000.
• 1 ≦K ≦N.
第17 回日本情報オリンピック(JOI 2017/2018) 本選
2018 年2 月11 日(茨城県つくば市)
• 1 ≦Ti ≦1 000 000 000 (1 ≦i ≦N).
• Ti < Ti+1 (1 ≦i ≦N −1).
예제 1
입력
3 2
1
3
6
출력
4
예제 2
입력
3 1
1
2
6
출력
6
예제 3
입력
3 3
1
3
6
출력
3
예제 4
입력
10 5
1
2
5
6
8
11
13
15
16
20
출력
12
문제 정보