Cod sursa(job #1139533)

Utilizator omerOmer Cerrahoglu omer Data 11 martie 2014 11:29:30
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include<stdio.h>
#include<deque>
using namespace std;
FILE *f,*g;
deque<int> mini;
float val[30001];
int cost[30001],timp[30001],U,L,n;
void add(int a)
{
    while (!mini.empty()&&val[mini.back()]>val[a]) mini.pop_back();
    mini.push_back(a);
}
int uberadd(int a)
{
    int q=mini.front();
    if (q==a-U+L-1) mini.pop_front();
    add(a);
    return q;
}
void initialization(void)
{
    int i;
    mini.clear();
    for(i=0;i<=U-L;i++) add(i);
}
void create(float x)
{
    int i;
    for(i=1;i<=n;i++)
    {
        val[i]=(cost[i]-x*timp[i])+val[i-1];
    }
}
bool verify(void)
{
    int i,q;
    initialization();
    for(i=U-L+1;i<=n-L+1;i++)
        {
            q=uberadd(i);
            if (val[i+L-1]-val[q]>0) return 1;
        }
    return 0;
}
float binsearch(void)
{
    float left=0,right=1000,mid;
    while(right-left>=0.0001)
        {
            mid=(left+right)/2;
            create(mid);
            if (verify()) left=mid;
            else right=mid;
        }
    return left;
}

int main()
{
    int i;
    f=fopen("secv3.in","r");
    g=fopen("secv3.out","w");
    fscanf(f,"%d%d%d",&n,&L,&U);
    for(i=1;i<=n;i++) fscanf(f,"%d",&cost[i]);
    for(i=1;i<=n;i++) fscanf(f,"%d",&timp[i]);
    fprintf(g,"%.2lf",binsearch());
    return 0;
}