Cod sursa(job #846822)

Utilizator marinutzacatana marina marinutza Data 2 ianuarie 2013 20:34:41
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
#define nmax 30010
int s[nmax],t[nmax],n,p,u,i,k,l;
double bs,a,b,c;
deque <int> deq;
int main()
{
    f>>n>>p>>u;
    for(i=1;i<=n;i++)
    {
        f>>s[i];
        s[i]+=s[i-1];
    }
    for(i=1;i<=n;i++)
    {
        f>>t[i];
        t[i]+=t[i-1];
    }
    t[0]=1;
    bs=(double)s[p]/t[p];
    for(i=0;i<=n-p;i++)
    {
        a=(double)s[i]/t[i];
        if(!deq.empty())
        b=(double)s[deq.back()]/t[deq.back()];
        while(!deq.empty() && a<b)
            deq.pop_back();
        deq.push_back(i);
        if(i-deq.front()>u-p)
            deq.pop_front();
        k=s[p+i]-s[deq.front()];
        l=t[p+i]-t[deq.front()];
        c=(double)k/l;
        if(c>bs)
           bs=c;
    }
    if(p==1 && bs<(double)(s[n]-s[n-1])/(t[n]-t[n-1]))
        bs=(double)(s[n]-s[n-1])/(t[n]-t[n-1]);
    g<<bs;
    return 0;
}