Cod sursa(job #638188)

Utilizator klamathixMihai Calancea klamathix 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;
}