Cod sursa(job #2777649)
Utilizator | Girbovan Robert Luca BlueLuca888 | Data | 23 septembrie 2021 20:13:50 |
---|---|---|---|
Problema | Zombie | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.37 kb |
#include <bits/stdc++.h>
#define MAXN 1000000
#define solve using namespace std;ifstream fin ("zombie.in");ofstream fout ("zombie.out");int dp[MAXN+5], v[MAXN+5], poz[MAXN+5];int d, n, k, p;int main(){fin>>d>>n>>k;for(int i=1; i<=n; i++){fin>>v[i];while(v[p] + d < v[i])p++;poz[i]=p;}for(int i=1; i<=n; i++)dp[i] = min(dp[i-1]+1, dp[poz[i]-1]+k);fout<<dp[n];return 0;}
solve