Cod sursa(job #1146279)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 18 martie 2014 20:45:26
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <deque>

#define DN 30005
using namespace std;

ifstream f("secv3.in");
ofstream g("secv3.out");

int n,l,u,v[DN],t[DN];
deque < int > q;


void read(){

    f>>n>>l>>u;
    for(int i=1;i<=n;++i)
        f>>v[i];
    for(int i=1;i<=n;++i)
        f>>t[i];
}

bool check(double timp){

    double S[DN];
    S[0] = 0;
    for(int i=1;i<=n;++i)
        S[i]= S[i-1] + 1.0 * v[i] - 1.0 * t[i] * timp;
    q.clear();
    if(S[l] >= 0)
        return true;

    for(int i = l;i<=n;++i){

        while( q.size() && S[ q.back() ] >= S[ i - l ])
            q.pop_back();
        while( q.size() && q.front() < i - u)
            q.pop_front();
        q.push_back( i - l);
        if(S[i] - S[ q.front() ] >= 0)
            return true;
    }
    return false;
}

void solve(){

    double st = 0 , dr = 2000 , mij , rez;
    while( st<=dr ){

        mij = ( st + dr)*0.5;
        cout<<mij<<" "<<check(mij)<<endl;
        if(check(mij)){

            rez = mij;
            st = mij + 1e-2;
        }else
            dr = mij - 1e-2;
    }
    g<< fixed << setprecision(2)<<rez;
}

int main()
{
    read();
    solve();

    return 0;
}