Pagini recente » Borderou de evaluare (job #2085890) | Cod sursa (job #525634) | Cod sursa (job #3238225) | Cod sursa (job #890998) | Cod sursa (job #2768393)
#include <bits/stdc++.h>
#define EPS 0.000000001
using namespace std;
typedef long long ll;
double v[100001],s[100001];
int st,dr,n,d;
bool good(double x)
{double minime[100001];
minime[0]=0;
minime[1]=v[1]-x;
for (int i=2;i<=n;i++) minime[i]=min(minime[i-1],s[i]-i*x);
//for (int i=1;i<=n;i++) cout<<s[i]<<' '<<minime[i]<<'\n';
for (int i=d;i<=n;i++) if (s[i]-i*x>=minime[i-d]) {dr=i; return 1;}
return 0;
}
int main()
{
cin>>n>>d;
for (int i=1;i<=n;i++) cin>>v[i];
for (int i=1;i<=n;i++) s[i]=s[i-1]+v[i];
double mij,l=0,r=100+EPS;
if (n==d) cout<<1<<' '<<n;
else{
while (r-l>=EPS) {mij=(l+r)/2;
if (good(mij)) l=mij;
else r=mij;
}
//cout<<24/5.0<<'\n';
for (int i=dr-d+1;i>=1;i--) {//cout<<(s[dr]-s[i-1])/(dr-i+1)<<' ';
if (abs((s[dr]-s[i-1])/(dr-i+1)-l)<EPS) st=i;
}
//cout<<'\n';
//cout<<(s[5]-s[2])/3-l<<'\n';
//cout<<l<<' '<<st<<' '<<dr;
cout<<st<<' '<<dr;
}
}