Cod sursa(job #1732788)

Utilizator borcanirobertBorcani Robert borcanirobert Data 22 iulie 2016 15:55:29
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;

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

const int MAXN = 30005;
const int MAXNR = 100005;
int N, L, U;
int a[MAXN];
int b[MAXN];
int v[MAXN];
int minim[MAXN];
int rez;
deque<int> Q;

void Read();
void CautareBinara();
bool Verificare( int x );

int main()
{
    Read();
    CautareBinara();

    fout << fixed << setprecision(2) << ((double)rez) / 100.0 << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int i;

    fin >> N >> L >> U;
    for ( i = 1; i <= N; i++ )
    {
        fin >> a[i];
        a[i] = 100 * a[i];
    }
    for ( i = 1; i <= N; i++ )
        fin >> b[i];
}

void CautareBinara()
{
    int st = 0, dr = MAXNR, mid;

    while ( st <= dr )
    {
        mid = ( st + dr ) / 2;

        if ( Verificare(mid) )
        {
            st = mid + 1;
            rez = mid;
        }
        else
            dr = mid - 1;
    }
}

bool Verificare( int x )
{
    int i;

    Q.clear();
    Q.push_back(0);

    for ( i = 1; i <= N; i++ )
        v[i] = v[i - 1] + a[i] - ( b[i] * x );

    for ( i = 1; i < N; i++ )
    {
   //     if ( x >= 78 && x <= 83 )
    //        fout << "DA";

        while ( !Q.empty() && i - Q.front() >= U )
            Q.pop_front();

        while ( !Q.empty() && v[i] <= v[Q.back()] )
            Q.pop_back();
        Q.push_back(i);

      //  int y = Q.front();
        minim[i] = v[Q.front()];
    }

    if ( U == 0 )
        for ( i = 1; i <= N; i++ )
            minim[i] = v[i];

    for ( i = 1; i <= N; i++ )
    {
        if ( v[i] - minim[i - 1] >= 0 )
            return true;
        if ( i <= L && v[i] >= 0 )
            return true;
    }

    return false;
}