Cod sursa(job #2974377)

Utilizator emazareMazare Emanuel emazare Data 3 februarie 2023 22:34:55
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

const int LMAX = 30005;
int c[LMAX],t[LMAX],c1[LMAX];
long long s[LMAX];
deque<int> dq;

bool verif(int v[], int n, int k, int w){
    int i;
    long long smax;
    for(i=1;i<=n;i++)
        s[i] = s[i-1]+(long long)v[i];
    dq.push_back(0);
    smax = s[k];
    for(i=k+1;i<=n;i++){
        while(!dq.empty() && s[i-k]<s[dq.back()])
            dq.pop_back();
        dq.push_back(i-k);
        if(dq.front()<i-w)
            dq.pop_front();
        smax = max(smax, s[i]-s[dq.front()]);
    }
    for(i=1;i<=n;i++)
        s[i] = 0;
    while(!dq.empty())
        dq.pop_back();
    if(smax>=0)
        return 1;
    return 0;
}

int main()
{
    int N,L,U,i,st,dr,mid,sol;
    double nr;
    fin >> N >> L >> U;
    for(i=1;i<=N;i++){
        fin >> c[i];
        c[i]*=100;
        c1[i] = c[i];
    }
    for(i=1;i<=N;i++)
        fin >> t[i];
    st = 0; dr = 100005; sol = 0;
    while(st<=dr){
        mid = (st+dr)/2;
        for(i=1;i<=N;i++)
            c[i] = c1[i]-mid*t[i];
        if(verif(c,N,L,U)){
            sol = mid;
            st = mid+1;
        }
        else
            dr = mid-1;
    }
    nr = (sol*1.0)/100;
    fout << nr;
    return 0;
}