Cod sursa(job #638453)

Utilizator irene_mFMI Irina Iancu irene_m Data 20 noiembrie 2011 21:26:10
Problema Zombie Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>

const int MAX_N = 1000005;
int d[ MAX_N ], zombie[ MAX_N ], N, D, K;

void read(){
    freopen( "zombie.in", "r", stdin );
    scanf( "%d %d %d", &D, &N, &K );
    for( int i = 1; i <= N; ++i )
        scanf( "%d", &zombie[ i ] );
}

int minim( int x, int y ){
    if( x < y )
        return x;
    return y;
}

void solve(){
    int i, j = 1;

    d[ 1 ] = 1;
    for( i = 2; i <= N; ++i ){
        while( zombie[ i ] - zombie[ j ] >= D )
            j++;

        d[ i ] = minim( d[ i - 1 ] + 1, d[ j - 1 ] + K );
    }
}

void write(){
    freopen( "zombie.out", "w", stdout );
    printf( "%d\n", d[ N ] );
}

int main(){
    read();
    solve();
    write();
    return 0;

}