Cod sursa(job #985034)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 16 august 2013 11:54:23
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
double Cost[302],Time[30002],Partial[30002];
int length,start,fin,C=1<<28,N,L,U,Deque[30002];
void Read()
{
    int i,value;
    f>>N>>L>>U;
    for(i=1;i<=N;i++)
    {
        f>>value;
        Cost[i]=value;
    }
    for(i=1;i<=N;i++)
    {
        f>>value;
        Time[i]=value;
    }
}
bool Calculate(double val)
{
    int i;
    int End=0,Begin=1;
    for(i=1;i<=N;i++)
        Partial[i]=Partial[i-1]+Cost[i]-Time[i]*val;
    if(Partial[L]>0)
        return 1;
    for(i=L+1;i<=N;i++)
    {
        while(End>=Begin && Partial[i-L]<Partial[Deque[End]])
            End--;
        Deque[++End]=i-L;
        if(Deque[Begin]==i-U-1)
            Begin++;
       if(Partial[i]>Partial[Deque[Begin]])
            return 1;
    }
    return 0;
}
void Binary_Search()
{
    double st=0,dr=1<<28,mid,sol;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(Calculate(mid)==1)
        {
            sol=mid;
            st=mid+0.001;
        }
        else
            dr=mid-0.001;
    }
    g<<fixed<<setprecision(6)<<sol<<"\n";
}
int main()
{
    Read();
    Binary_Search();
    return 0;
}