Cod sursa(job #636973)

Utilizator Fetita_JucausaFetita Buclucasa Fetita_Jucausa Data 20 noiembrie 2011 08:47:27
Problema Zombie Scor 70
Compilator cpp Status done
Runda .com 2011 Marime 0.58 kb
#include <algorithm>
#include <cstdio>
using namespace std;

#define MaxN 1000005

int v[MaxN],bst[MaxN];
int N,D,cst;

void read ()
{
    scanf ("%d%d%d",&D,&N,&cst);
    for (int i=1; i<=N; ++i)
        scanf ("%d",&v[i]);
}

void solve ()
{
    int last=1;

    for (int i=1; i<=N; ++i)
    {
        for ( ; v[last]+D<v[i]; ++last);
        bst[i]=min (bst[i-1]+1,bst[last-1]+cst);
    }

    printf ("%d",bst[N]);
}

int main ()
{
    freopen ("zombie.in","r",stdin);
    freopen ("zombie.out","w",stdout);

    read ();
    solve ();

    return 0;
}