Cod sursa(job #2021726)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 14 septembrie 2017 15:53:01
Problema Zombie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[1000001];
int main()
{
    FILE *fin=fopen ("zombie.in","r");
    FILE *fout=fopen ("zombie.out","w");
    int d,n,k,i,sol,st,dr,mid;
    fscanf (fin,"%d%d%d",&d,&n,&k);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d",&v[i]);
    sort (v+1,v+n+1);
    sol=0;
    for (i=1;i<=n;i++){
        // caut cel mai mare nr mai mic sau egal ca v[i]+d-1
        st=i;
        dr=n;
        while (st<=dr){
            mid=(st+dr)/2;
            if (v[mid]>v[i]+d-1)
                dr=mid-1;
            else st=mid+1;
        }
        if (dr-i+1>=k){
            sol+=k;
            i=dr;
        }
        else sol++;
    }
    fprintf (fout,"%d",sol);
    return 0;
}