Cod sursa(job #638565)
Utilizator | Moraru Valentina valentina506 | Data | 20 noiembrie 2011 22:41:50 |
---|---|---|---|
Problema | Zombie | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.41 kb |
#include<fstream>
#include<algorithm>
using namespace std;
unsigned long i,j,n,m,d,k,a[1000001],b[1000002];
int main()
{
freopen("zombie.in","r",stdin);
freopen("zombie.out","w",stdout);
scanf("%ld%ld%ld",&d,&n,&k);
for(i=1;i<=n;++i)
scanf("%ld",&a[i]);
b[n]=1;
b[n+1]=0;
m=n;
i=n-1;
while(i)
{
i--;
while(a[m]-a[i]>=d&&m>i)
--m;
b[i]=min(1+b[i+1],b[m+1]+k);
}
printf("%ld ",b[1]);
return 0;
}