Cod sursa(job #2782535)

Utilizator Asgari_ArminArmin Asgari Asgari_Armin Data 12 octombrie 2021 17:28:46
Problema Zombie Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "zombie.in" );
ofstream fout( "zombie.out" );

const int NMAX = 1e6;
int v[NMAX + 2], dp[NMAX + 2], newone[NMAX + 2];

int main() {
  int d, k, n, i, j;
  fin >> d >> n >> k;
  for( i = 1; i <= n; ++i )
    fin >> v[i];

  j = 1;
  for( i = 1; i <= n; ++i ){
    while( v[j] + d <= v[i] + 1 )
      ++j;
    newone[i] = j;
  }

  dp[1] = 1;
  for( i = 2; i <= n; ++i )
    dp[i] = min(dp[i - 1] + 1, dp[newone[i] - 1] + k);
  fout << dp[n];
  return 0;
}