Cod sursa(job #3140421)

Utilizator petric_mariaPetric Maria petric_maria Data 6 iulie 2023 09:49:22
Problema Zombie Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 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;
    i=j=1; v[1]=1; x=1; f>>a[1];
    while(j<n){
        ++j; f>>a[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=n; j=n; ans=0;
    while(i>=1){
        i--;
        if(j-i==v[i+1]){
            if(v[i+1]>=k) ans+=k;
            else ans+=(j-i);
            j=i;
        }
    }
    if(j-i==v[i+1]){
        if(v[i+1]>=k) ans+=k;
        else ans+=v[i+1];
    }
    else{
        if((j-i)>=k) ans+=k;
        else ans+=(j-i);
    }
    g<<ans;
    return 0;
}