Pagini recente » Cod sursa (job #1119198) | Cod sursa (job #1017750) | Cod sursa (job #1582717) | Cod sursa (job #1775790) | Cod sursa (job #890355)
Cod sursa(job #890355)
#include <cstdio>
#define NMax 1000005
using namespace std;
int D, N, K, DP[NMax], Prev[NMax], T[NMax];
inline int Min (int a, int b)
{
if (a<b)
{
return a;
}
return b;
}
int main()
{
freopen ("zombie.in", "r", stdin);
freopen ("zombie.out", "w", stdout);
scanf ("%d %d %d", &D, &N, &K);
for (int i=1; i<=N; ++i)
{
scanf ("%d", &T[i]);
if (T[i]-T[Prev[i-1]]<D)
{
Prev[i]=Prev[i-1];
}
else
{
Prev[i]=Prev[i-1];
for (int j=Prev[i-1]+1; T[i]-T[j]>=D; ++j)
{
Prev[i]=j;
}
++Prev[i];
}
if (i==1)
{
Prev[i]=i;
}
DP[i]=Min (DP[i-1]+1, DP[Prev[i]-1]+K);
/*DP[i]=DP[i-1]+1;
for (int j=i-1; j>0 and T[i]-T[j]<D; --j)
{
DP[i]=Min (DP[i], DP[j-1]+K);
}*/
}
printf ("%d\n", DP[N]);
return 0;
}