Cod sursa(job #1732797)

Utilizator borcanirobertBorcani Robert borcanirobert Data 22 iulie 2016 16:18:46
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 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;
long long N, L, U;
long long a[MAXN];
long long b[MAXN];
long long v[MAXN];
long long minim[MAXN];
long long rez;
long long k;
deque<long long> Q;

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

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

    double x = rez;
    x /= 100;

    fout << x << '\n';

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

void Read()
{
    long long i;

    fin >> N >> L >> U;
    k = U - L;
    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()
{
    long long st = 50, dr = 100, mid;

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

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

bool Verificare( long long x )
{
    long long 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 = L; i <= N; i++ )
    {
   //     if ( x == 389 )
   //         fout << "DA";

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

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

        if ( v[i] - v[Q.front()] >= 0 )
            return true;
    }

    return false;
}