Cod sursa(job #3308499)

Utilizator Maryy_1369Gociu Maria Anastasia Maryy_1369 Data 25 august 2025 16:32:05
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include<deque>
#include<algorithm>
using namespace std;
ifstream cin("secv3.in");
ofstream cout("secv3.out");
long long c[30005], t[30005], sum[30005];
int l,u,n;

bool eok(int x){
   for(int i=1;i<=n;i++){
     sum[i]=sum[i-1]+c[i]*100-x*t[i];
   }
   deque<int>v;
   for(int i=l;i<=n;i++){
      if(v.front()<i-u)v.pop_front();
      while(!v.empty() && sum[v.back()]> sum[i-l]){
         v.pop_back();
      }
      v.push_back(i-l);
      if(sum[i]-sum[v.front()]>=0)return true;
   }
   return false;
}
int main()
{
    cin>>n>>l>>u;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    for(int i=1;i<=n;i++){
        cin>>t[i];
    }
    long long st=0,dr=3*1e7*100,ans=0;
    while(st<=dr){
        long long mij=(st+dr)/2;
        if(eok(mij)==true){
            ans=mij;
            st=mij+1;
        }
        else{
            dr=mij-1;
        }
    }
    cout<<ans/100.0;
}