Cod sursa(job #637928)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 20 noiembrie 2011 17:36:46
Problema Zombie Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 0.44 kb
#include<stdio.h>
#define Nmax 1000009
#define min(a,b) ((a<b) ? a:b)

int a[Nmax],b[Nmax],sol[Nmax],i,N,st,cost,K;

int main()
{
	freopen("zombie.in","r",stdin);
	freopen("zombie.out","w",stdout);
	
	scanf("%d%d%d",&K,&N,&cost);
	
	st=1;
	for (i=1;i<=N;i++)
	{
		scanf("%d",&a[i]);
		while (a[i]-K>=a[st])
			st++;
		b[i]=st-1;
	}
	
	for (i=1;i<=N;i++)
		sol[i]=min(sol[i-1]+1,sol[b[i]]+cost);
	printf("%d\n",sol[N]);
}