Cod sursa(job #1023700)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 7 noiembrie 2013 16:41:55
Problema Zombie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#define LMAX 1000100

int x[LMAX];

int main ()
{
    int D, N, K, i, left, right, med, sum = 0;

    freopen ("zombie.in", "r", stdin);
    freopen ("zombie.out", "w", stdout);

    scanf ("%d%d%d", &D, &N, &K);
    for (i = 1; i <= N; i ++)
        scanf ("%d", &x[i]);

    for (i = 1; i <= N; i ++)
    {
        left = i; right = N;
        while (left <= right)
        {
            med = (left + right) / 2;
            if (x[i] + D - 1 >= x[med])
                left = med + 1;
            else
                right = med - 1;
        }

        if (x[left] != x[i] + D - 1)
            left --;
        if (left > K)
            sum += K, i = left;
        else
            sum ++;
    }

    printf ("%d", sum);
    return 0;
}