Cod sursa(job #1732754)

Utilizator borcanirobertBorcani Robert borcanirobert Data 22 iulie 2016 15:17:00
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 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 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 = 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( 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();

      //  int y = Q.front();
        if ( i >= L && i - Q.front() >= L && v[i] - v[Q.front()] >= 0 )
            return true;

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