Cod sursa(job #890355)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 25 februarie 2013 00:14:36
Problema Zombie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#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;
}