Cod sursa(job #2768393)

Utilizator RK13Barbu Eduard RK13 Data 10 august 2021 16:56:08
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#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;
}
}