Cod sursa(job #2059325)

Utilizator mihai.alphamihai craciun mihai.alpha Data 6 noiembrie 2017 21:21:38
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e4+5;
int n,l,u,i,c[MAXN],t[MAXN];
deque<int>q;
int main(){
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    cin>>n>>l>>u;
    for(i=1;i<=n;i++)
        cin>>c[i],c[i]+=c[i-1];
    for(i=1;i<=n;i++)
        cin>>t[i],t[i]+=t[i-1];
    double ans=1.0*c[l]/t[l];
    for(i=l;i<=n;i++)  {
        while(q.size()&&q.front()<=i-u)
              q.pop_front();
        while(q.size()&&1LL*(c[i]-c[q.back()-1])*(t[i]-t[i-l])<1LL*(c[i]-c[i-l])*(t[i]-t[q.back()-1]))
              q.pop_back();
        q.push_back(i-l+1);
        ans = max(ans,1.0*(c[i]-c[q.front()-1])/(t[i]-t[q.front()-1]));}
    printf("%.2lf",ans);
    return 0;}