Mai intai trebuie sa te autentifici.
Cod sursa(job #2773505)
Utilizator | Data | 7 septembrie 2021 12:42:50 | |
---|---|---|---|
Problema | Zombie | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.82 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("zombie.in");
ofstream fout ("zombie.out");
int st, md, dr;
int d, n, k, x, lst;
int v[1000005], dp[1000005];
long long s[1000005];
int main (){
fin>>d>>n>>k>>lst;
for(int i=1; i<n; i++){
fin>>x;
v[i]=x-lst;
lst=x;
}
for(int i=1; i<k; i++){
dp[i]=dp[i-1]+1;
s[i]=s[i-1] + v[i];
}
for(int i=k; i<n; i++){
x=v[i];
s[i]=s[i-1] + x;
st=1;
dr=i-k+1;
while(st <= dr){
md=(dr-st)/2+st;
if(s[i]-s[md-1] >= d)
st=md+1;
else
dr=md-1;
}
//cout<<st<<" ";
dp[i]=min(dp[i-1]+1, dp[st-1]+k);
}
fout<<dp[n-1];
return 0;
}