Cod sursa(job #1993424)

Utilizator Y0da1NUME JMECHER Y0da1 Data 22 iunie 2017 23:28:39
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
int N, L, U;
int cost [30002];
int timp [30002];
double medii [30002];
double sum [30002];
int interval[30002];
deque <pair <int, int> > D;
int main ()
{
    int i, k;

    ifstream in ("secv3.in");
    ofstream out ("secv3.out");
    pair <int, int> x;
    bool posibil;
    in>>N>>L>>U;
    k=U-L+1;
    for (i=1;i<=N;++i)
        in>>cost[i];
    for (i=1;i<=N;++i)
        in>>timp[i];
    //cout<<endl;
    double lo = 0, hi = 30000001, mid;
    while(hi-lo>=0.01)
    {
        mid = (lo + hi)/2;
        posibil = false;
        //cout<<lo<<" "<<mid<<" "<<hi<<"\n";
        for(i=1;i<=N;++i)
        {
            medii[i]=cost[i]-mid*(double)timp[i];
            sum[i]=sum[i-1]+medii[i];
            //cout<<sum[i]<<" ";
        }
        //cout<<"\n";
        while(!D.empty())
            D.pop_front();
        for(i=1;i<=N;++i)
        {
            x.first = i;
            x.second = sum[i];
            if(!D.empty() && D.front().first <= i-k)
                D.pop_front();
            while (!D.empty() && D.back().second >=x.second)
            {
                D.pop_back();
            }
            D.push_back(x);
            interval[i]=D.front().first;   //pozitia minimului din intervalu care se termina pe pozitia i
        }
        //cout<<"\n"<<D.empty();
        for(i=L;i<=N;++i)
        {
            if(sum[i]-sum[interval[i-L]] >= 0)  //se poate un rezultat mai mare
                posibil=true;
        }
        if(posibil)
            lo=mid;
        else
            hi=mid;
    }
    //cout<<mid;
    out<<fixed<<setprecision(2)<<mid;



}