Cod sursa(job #1989803)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 8 iunie 2017 22:30:47
Problema Zombie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<fstream>
using namespace std;
ifstream in("zombie.in");
ofstream out("zombie.out");
int st,dr,k,d,n,v[1000001],dp[1000001],i,ans[1000001];
int main(){
    in >> d >> n >> k;
    for( i = 1; i <= n; i ++ ){
        in >> v[i];
    }
    for( st = 1, dr = 1; dr <= n; dr ++ ){
        while( st <= dr && v[dr] - v[st] >= d ){
            st++;
        }
        dp[dr] = st;
    }
    for( i = 1; i <= n; i ++ ){
        ans[i] = min( ans[dp[i-1]] + k, ans[dp[i-1]] + 1 );
    }
    out<<ans[n];
    return 0;
}