Cod sursa(job #637830)

Utilizator irene_mFMI Irina Iancu irene_m Data 20 noiembrie 2011 17:04:07
Problema Zombie Scor 30
Compilator cpp Status done
Runda .com 2011 Marime 0.72 kb
#include <cstdio>

const int MAX_N = 1000002;
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 ){
        if( 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;

}