Cod sursa(job #1989806)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 8 iunie 2017 22:34:43
Problema Zombie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 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[i-1] + 1 );
    }
    out<<ans[n];
    return 0;
}