codeforces-508C -鬼吹灯（巧妙模拟）

 C. Anya and Ghosts time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Anya loves to watch horror movies. In the best traditions of horror, she will be visited by m ghosts tonight. Anya has lots of candles prepared for the visits, each candle can produce light for exactly t seconds. It takes the girl one second to light one candle. More formally, Anya can spend one second to light one candle, then this candle burns for exactly t seconds and then goes out and can no longer be used.

For each of the m ghosts Anya knows the time at which it comes: the i-th visit will happen w_i seconds after midnight, all w_i's are distinct. Each visit lasts exactly one second.

What is the minimum number of candles Anya should use so that during each visit, at least r candles are burning? Anya can start to light a candle at any time that is integer number of seconds from midnight, possibly, at the time before midnight. That means, she can start to light a candle integer number of seconds before midnight or integer number of seconds after a midnight, or in other words in any integer moment of time.

Input

The first line contains three integers m, t, r (1 ≤ m, t, r ≤ 300), representing the number of ghosts to visit Anya, the duration of a candle's burning and the minimum number of candles that should burn during each visit.

The next line contains m space-separated numbers w_i (1 ≤ i ≤ m, 1 ≤ w_i ≤ 300), the i-th of them repesents at what second after the midnight the i-th ghost will come. All w_i's are distinct, they follow in the strictly increasing order.

Output

If it is possible to make at least r candles burn during each visit, then print the minimum number of candles that Anya needs to light for that.

If that is impossible, print  - 1.

Examples input 1 8 3 10 output 3 input 2 10 1 5 8 output 1 input 1 1 3 10 output -1 题意：假如一天晚上有M只鬼要去拜访你家，每欢迎一只鬼的到来需要点r根蜡烛，每根蜡烛的 持续时间为t秒，点蜡烛需要消耗1秒，并且每只鬼在你家只待一秒，问你至少需要点多少蜡烛 才能让所有鬼开心，如果无法满足则输出-1. 题解：此题为典型贪心，要想保证燃烧蜡烛最少只需在鬼来之前点蜡烛即可。 具体过程看代码： #include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> using namespace std; #define maxn 1005 int flag[maxn],vis[maxn];//flag数组标记当前位置有多少根蜡烛在燃烧，vis表示当前位置是否已经点燃蜡烛 int main() { int n,m,i,j,a[maxn],t,r,sum; while(scanf("%d%d%d",&m,&t,&r)!=EOF) { sum=0; memset(flag,0,sizeof(flag)); memset(vis,0,sizeof(vis)); for(i=1;i<=m;i++) { scanf("%d",&a[i]); a[i]+=500; } for(i=1;i<=m;i++) { if(flag[a[i]]>=r) continue; else { for(j=a[i]-1;j>=a[i]-t;j--) { if(vis[j]==0) { sum++; vis[j]=1; for(int k=j+1;k<=j+t;k++) flag[k]++; } if(flag[a[i]]>=r) break; } } if(flag[a[i]]<r) { sum=-1; break; } } printf("%d\n",sum); } }