#PU715. USACO 2017 February Contest, Silver — Problem 2. Why Did the Cow Cross the Road II

    ID: 1366 传统题 文件IO:maxcross 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:feb17来源:usaco.orgscoring:equal_test_cases区间DP

USACO 2017 February Contest, Silver — Problem 2. Why Did the Cow Cross the Road II

USACO 2017 February Contest, Silver — Problem 2. Why Did the Cow Cross the Road II

题目描述

The long road through Farmer John's farm has NN crosswalks across it, conveniently numbered 1…N1 \ldots N (1≤N≤100,0001 \leq N \leq 100,000). To allow cows to cross at these crosswalks, FJ installs electric crossing signals, which light up with a green cow icon when it is ok for the cow to cross, and red otherwise. Unfortunately, a large electrical storm has damaged some of his signals. Given a list of the damaged signals, please compute the minimum number of signals that FJ needs to repair in order for there to exist some contiguous block of at least KK working signals.

输入格式

The first line of input contains NN, KK, and BB (1≤B,K≤N1 \leq B, K \leq N). The next BB lines each describe the ID number of a broken signal.

输出格式

Please compute the minimum number of signals that need to be repaired in order for there to be a contiguous block of KK working signals somewhere along the road.

数据范围

(见题面原文)

样例

样例 1

10 6 5
2
10
1
5
9
1
Problem credits: Brian Dean