Cod sursa(job #735792)
Utilizator | cristescu liviu ms-ninja | Data | 17 aprilie 2012 12:17:10 |
---|---|---|---|
Problema | Zombie | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.45 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 1000010
int d, n, k, p1;
int v[maxn], dp[maxn];
int main()
{
freopen("zombie.in", "r", stdin);
freopen("zombie.out", "w", stdout);
scanf("%d%d%d", &d, &n, &k);
p1=1;
for(int i=1; i<=n; ++i)
{
scanf("%d", &v[i]);
while(v[i]-v[p1]>=d)
++p1;
dp[i]=min(dp[i-1]+1, dp[p1-1]+k);
}
printf("%d\n", dp[n]);
return 0;
}