Cod sursa(job #723917)

Utilizator mening12001Andrei Geogescu mening12001 Data 26 martie 2012 01:10:06
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<fstream>
#include<deque>
#define inf 0x3f3f3f3f
using namespace std;
long s[30000],ss[30000];
int main()
{ifstream f("secv3.in");
ofstream h("secv3.out");
int L,U,n,i,a;
float max=-inf;
deque<int> p;
f>>n>>L>>U;
for(i=1;i<=n;i++)
	{f>>a;
s[i]=s[i-1]+a;}
for(i=1;i<=n;i++)
	{f>>a;
ss[i]=ss[i-1]+a;}
	
for(i=1+L;i<=n;i++)
	{	while(!p.empty()&&s[i]>p.back())
			p.pop_back();
		p.push_back(i-L);
		if(p.front()<i-U-1)
			p.pop_front();
		int min=p.front();
			if((s[i]-s[min])*1./(ss[i]-ss[min])>max)
		max=(s[i]-s[min])*1./(ss[i]-ss[min]);
	}
		h<<max;	
	return 0;}