Cod sursa(job #1733179)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 23 iulie 2016 21:04:20
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <algorithm>
#include <deque>
#define MaxN 30001
#define INF 2000000000
#define time second
#define value first
using namespace std;

pair <int,int> v[MaxN];
int N,U,L;
float Max;
deque <int>D;
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
	scanf("%d%d%d",&N,&L,&U);
	v[0].value=v[0].time=0;
	for(int i=1;i<=N;i++)
		scanf("%d",&v[i].value),v[i].value+=v[i-1].value;
	for(int i=1;i<=N;i++)
		scanf("%d",&v[i].time),v[i].time+=v[i-1].time;
	for(int i=L;i<=N;i++)
	{
		while(!D.empty()&&1.0f*v[D.back()].value/v[D.back()].time>1.0f*v[i-L].value/v[i-L].time)
			D.pop_back();
		D.push_back(i-L);
		if(D.front()<=i-U)
			D.pop_front();
		if(Max<1.0f*(v[i].value-v[D.front()].value)/(v[i].time-v[D.front()].time))
		{
			Max=1.0f*(v[i].value-v[D.front()].value)/(v[i].time-v[D.front()].time);
		}
	}
	printf("%.2f",Max);
	return 0;
}