Cod sursa(job #3293289)

Utilizator unomMirel Costel unom Data 11 aprilie 2025 12:24:39
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

#define int long long

ifstream in("secv3.in");
ofstream out("secv3.out");
int n, x, y;
int a[30005];
int b[30005];
int sp[30005];

int check(int t)
{
    for(int i = 1; i<=n; i++)
    {
        sp[i] = a[i] * 100 - b[i] * t;
        sp[i] += sp[i - 1];
    }

    deque<int> dq;
    for(int i = x; i<=n; i++)
    {
        while(!dq.empty() && sp[i - x] <= sp[dq.back()]) //e i - x, in loc de i - x + 1 ca e vector de sp
        {
            dq.pop_back();
        }

        dq.push_back(i - x);

        if(dq.front() == i - y - 1) //la fel si aici
        {
            dq.pop_front();
        }

        if(sp[i] - sp[dq.front()] >= 0)
        {
            return 1;
        }
    }

    return 0;
}

signed main()
{
    in>>n>>x>>y;

    for(int i = 1; i<=n; i++)
    {
        in>>a[i];
    }
    for(int i = 1; i<=n; i++)
    {
        in>>b[i];
    }

    int st = 1;
    int dr = 1e10;
    int ans, mij;

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

        if(check(mij))
        {
            ans = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }

    long double rez = (long double)ans / 100.0;

    out<<setprecision(2)<<fixed<<rez;

    return 0;
}