Cod sursa(job #1691123)

Utilizator Daria09Florea Daria Daria09 Data 16 aprilie 2016 22:08:00
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#define NMAX 3005
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int n,l,u,cost[NMAX],timp[NMAX],ind[NMAX];
double s[NMAX],d[NMAX];
bool okay(double k)
{
    int i,head=1,tail=0;
    double MAX=-2000000000;
    for(i=1;i<=n;i++)s[i]=s[i-1]+cost[i]-k*timp[i];
    for(i=l;i<=n;i++)
    {
        while(head<=tail&&ind[head]<i-u)head++;
        while(head<=tail&&d[tail]>s[i-l])tail--;
        tail++;
        d[tail]=s[i-l];
        ind[tail]=i-l;
        MAX=max(MAX,s[i]-s[ind[tail]]);
    }
    return (MAX>=0);
}
void solve()
{
    double head,tail,mij,sol; int i;
    f>>n>>l>>u;
    for(i=1;i<=n;i++)f>>cost[i];
    for(i=1;i<=n;i++)f>>timp[i];
    head=0; tail=2000;
    while(head<tail+0.00001)
    {
        mij=(head+tail)/2;
        if(okay(mij)){sol=mij;head=mij+0.00001;} else tail=mij-0.00001;
    }
    g<<setprecision(2)<<fixed<<sol;
}
int main()
{
    solve();
    return 0;
}