Cod sursa(job #638188)
| Utilizator | Data | 20 noiembrie 2011 19:26:03 | |
|---|---|---|---|
| Problema | Zombie | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | .com 2011 | Marime | 0.49 kb |
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
int i , j , n , v[maxn] , dp[maxn] , d, k;
int main()
{
freopen("zombie.in","r",stdin);
freopen("zombie.out","w",stdout);
scanf("%d %d %d",&d,&n,&k);
for ( i = 1 ; i <= n ; ++i )
scanf("%d",&v[i]);
for ( i = 1 , j = 1 ; i <= n ; ++i ) {
for ( ; (v[i] - v[j]) >= d && j < i ; ++j );
dp[i] = dp[j - 1] + min ( k , (i - j + 1));
}
printf("%d\n", dp[n]);
return 0;
}