Cod sursa(job #2777916)

Utilizator Ioana_8Ioana Stroe Ioana_8 Data 26 septembrie 2021 08:01:43
Problema Zombie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>

using namespace std;

ifstream cin ("zombie.in");
ofstream cout ("zombie.out");

int v[1000005], v2[1000005], d[1000005];

int main()
{
    int d, n, k, st=0, dr=0, sol=0, nr1, nr2;
    cin >> d >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    while (dr < n)
    {
        if (v[dr] <= v[st] + d)
            dr++;
        else
            st++;
        v2[dr] = st;
    }
    d[0] = 1;
    for (i = 1; i < n; i++)
    {
        nr1 = d[i - 1] + 1;
        nr2 = d[v2[i] - 1] + k;
        if (nr1 < nr2)
            d[i] = nr1;
        else
            d[i] = nr2;
    }
    cout << d[n - 1];
    return 0;
}