Cod sursa(job #635328)

Utilizator crushackPopescu Silviu crushack Data 19 noiembrie 2011 10:26:44
Problema Zombie Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 0.5 kb
#include <fstream>
#define NMax 1000010
using namespace std;

const char IN[]="zombie.in",OUT[]="zombie.out";

int D,N,K;
int a[NMax];
int T[NMax];

ifstream fin(IN); ofstream fout(OUT);

inline int min(int x,int y){
	return x<y ? x : y;
}

int main()
{
	int i,j;
	fin>>D>>N>>K;
	for (i=0;i<N;++i) fin>>a[i];
	
	for (i=j=N-1;i>=0;--i)
	{
		while (j>i && a[i]+D-1<a[j]) --j;
		T[i]= min( T[i+1] + 1 , K + T[j+1]);
	}
	
	//for (i=0;i<N;++i) printf("%d ",T[i]);printf("\n");
	fout<<T[0];
	fout.close();
	
	return 0;
}