Cod sursa(job #635636)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 19 noiembrie 2011 13:44:45
Problema Zombie Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 0.98 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 1000010

int A[MAXN],DP[MAXN];
int i,st;
int D,N,K;
char s[2*MAXN];

/*int cbin(int st, int L) {
	int dr,m,rez;
	dr=L; rez=L;
	m=(st+dr)/2;
	while(st<=dr) {
		if(A[L]-A[m]+1<=D) {
			rez=min(rez,m);
			dr=m-1;
		}
		else
			st=m+1;
		m=(st+dr)/2;
	}
	return rez;
}*/

int main() {
	freopen("zombie.in","r",stdin);
	freopen("zombie.out","w",stdout);
	
	scanf("%d %d %d\n",&D,&N,&K);
	
	//for(i=1;i<=N;i++)
	//	scanf("%d",&A[i]);
	fgets(s,sizeof(s),stdin);
	int cnt=0;
	for(i=0;i<=(int)sizeof(s);i++) {
		if(s[i]=='\0' || s[i]=='\n') break;
		while(s[i]==' ') i++;
		if(s[i]=='\0' || s[i]=='\n') break;
		
		cnt++;
		A[cnt]=0;
		for(;s[i]>='0' && s[i]<='9';i++)
			A[cnt]=10*A[cnt]+(s[i]-'0');
		
	}
	
	if(cnt!=N) for(;;);
	
	st=1; DP[1]=1;
	for(i=2;i<=N;i++) {
		//st=cbin(st,i);
		while(A[i]-A[st]+1>D)
			st++;
		DP[i]=min(DP[i-1]+1,DP[st-1]+K);
	}
	printf("%d",DP[N]);
}