Cod sursa(job #2973561)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 1 februarie 2023 10:49:32
Problema Zombie Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <fstream>
using namespace std;
const int NMAX = 1000000;
int v[NMAX + 1], dp[NMAX + 1], poz[NMAX + 1];
int main(){
  ifstream in("zombie.in");
  ofstream out("zombie.out");
  int d, n, k, p;
  in >> d >> n >> k;
  for( int i = 1 ; i <= n ; i++ )
    in >> v[i];
  p = 1;
  for( int i = 1 ; i <= n ; i++ ){
    while( v[p] + d < v[i] )
      p++;
    poz[i] = p;
  }
  dp[1] = 1;
  for( int i = 2 ; i <= n ; i++ )
    dp[i] = min (dp[i - 1] + 1, dp[poz[i] - 1] + k);
  out << dp[n];
  return 0;
}