Cod sursa(job #3304926)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 28 iulie 2025 18:54:16
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");

const int Nmax = 30000 + 5;
long long cost[Nmax], timp[Nmax], sp[Nmax], l, u, n;
bool valid( int x )
{
    int i;
    for ( i = 1; i <= n; ++i )
        sp[i] = sp[i - 1] + cost[i] * 100 - x * timp[i];

     deque <int> deq;
     for ( i = l; i <= n; ++i )
     {
         if ( deq.front() < i - u )
            deq.pop_front();

         while ( deq.empty() == false && sp[deq.back()] > sp[i - l] )
            deq.pop_back();
         deq.push_back(i - l);

         if ( sp[i] - sp[deq.front()] >= 0 )
            return true;
     }
     return false;

}
int main()
{
    int i;
    fin >> n >> l >> u;
    for ( i = 1; i <= n; ++i )
        fin >> cost[i];
    for ( i = 1; i <= n; ++i )
        fin >> timp[i];

    long long st = 0, dr = 3 * 1e7 * 100, mij, sol = 0;
    while ( st <= dr )
    {
        mij = (st + dr) / 2;
        if ( valid(mij) == true )
        {
            sol = mij;
            st = mij + 1;
        }
        else
            dr= mij - 1;
    }
    fout << fixed << setprecision(2) << sol / 100.0;
    return 0;
}