Cod sursa(job #2973561)
Utilizator | 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;
}