Cod sursa(job #3140286)

Utilizator petric_mariaPetric Maria petric_maria Data 5 iulie 2023 13:10:14
Problema Zombie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("zombie.in");
ofstream g("zombie.out");
int n,d,k,i,j,a[1000005],v[1000005],x,ans,ma;
int main()
{
    f>>d>>n>>k;
    for(i=1;i<=n;++i) f>>a[i];
    i=j=1; v[1]=1; x=1;
    while(j<n){
        ++j;
        if(a[j]-a[i]<d){ ++x;
            if(j==n) v[i]=x;
        }
        else{
            v[i]=x; ++i;
            while(a[j]-a[i]>=d){
                ++i; --x;
            }
            if(j==n) v[i]=x;
        }
    }
//    for(i=1;i<=n;++i) cout<<v[i]<<' ';
//    cout<<endl;
    i=1; ans=0;
    while(i<=n){
        ma=v[i]; x=i;
        for(j=i+1;j<=i+v[i] && j<=n;++j)
            if(v[j]>=ma){ ma=v[j]; x=j; }
        if(x==i){
            x=v[i];
            if(x>=k) ans+=k;
            else ans+=x;
            i+=x;
        }
        else{
            x=x-i;
            if(x>=k) ans+=k;
            else ans+=x;
            i+=x;

        }
    }
    g<<ans;
    return 0;
}