Cod sursa(job #3316647)

Utilizator Andreea1501013Andreea Andreea1501013 Data 19 octombrie 2025 16:39:18
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

int N,L,U,spCost[30005],spTimp[30005],cost,timp;

void citireSiSp()
{
    fin>>N>>L>>U;
    for(int i=1;i<=N;i++)
    {
        fin>>cost;
        spCost[i]=spCost[i-1]+cost;
    }
    for(int i=1;i<=N;i++)
    {
        fin>>timp;
        spTimp[i]=spTimp[i-1]+timp;
    }
}

bool f2(double x, int i, int j)
{
    double a = spCost[i] - x * spTimp[i];
    double b = spCost[j] - x * spTimp[j];
    return a < b;
}

bool check(double x)
{
    deque<int> dq;
    for(int i=1;i<=N;i++)
    {
        if(i>U)
        {
            if (dq.empty()==0 && dq.front()<i-U)
            {
                dq.pop_front();
            }
        }
        if(i>L)
        {
            while(dq.empty()==0 && f2(x,i-L,dq.back()))
            {
                dq.pop_back();
            }
            dq.push_back(i-L);
        }
        if(dq.empty()==0 && f2(x, i, dq.front())==0)
        {
            return 1;
        }
    }
    return 0;
}

void cautareBinara()
{
    double st=0, dr=1005,sol,x;
    ///log(1000) pana ajung cu st si dr la dist de 1, log(100) pana ajung la precision 2
    /// ~20 op
    for(int i=0;i<=100;i++)
    {
        x=(st+dr)/2;
        bool ok=check(x);
        if(ok==1)
        {
            /// x <= solutia cautata
            st=x;
            sol=x;
        }
        else
        {
            /// x > solutia cautata
            dr=x;
        }
    }
    fout<<fixed<<setprecision(3)<<sol;
}

int main()
{
    citireSiSp();
    cautareBinara();

    return 0;
}