Cod sursa(job #635469)
Utilizator | George Marcus PlayLikeNeverB4 | Data | 19 noiembrie 2011 11:57:12 |
---|---|---|---|
Problema | Zombie | Scor | 50 |
Compilator | cpp | Status | done |
Runda | .com 2011 | Marime | 0.43 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 1000010
int A[MAXN],DP[MAXN];
int i,st;
int D,N,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",&A[i]);
st=1; DP[1]=1;
for(i=2;i<=N;i++) {
while(A[i]-A[st]+1>D)
st++;
DP[i]=min(DP[i-1]+1,DP[st-1]+K);
}
printf("%d",DP[N]);
}