Cod sursa(job #2212693)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 14 iunie 2018 16:27:11
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
double cost[30001],timp[30001],v[30001];
int d[30001],st=0,dr=-1,n,u,l;
inline void stanga(int i)
{
 if(d[st]==i&&st<=dr)
        st++;
}
inline void dreapta(int i)
{
 while(st<=dr&&v[i]<=v[d[dr]])
        dr--;
 d[++dr]=i;
}
bool verif(double val)
{
 st=0;
 dr=-1;
 double max1=-1000000;
 int i;
 for(i=1;i<=n;i++)
        v[i]=cost[i]-(double)timp[i]*val+v[i-1];
 for(i=1;i<=n-l;i++)
 {
  stanga(i-u+l-1);
  dreapta(i);
  if(i>=l)
  max1=max(max1,v[i+l]-v[d[st]]);
 }
 if(max1>=0)
    return 1;
 return 0;
}
void cautbin()
{
 double r=0,pas=1<<14;
 while(pas>=0.001)
 {
  if(verif(r+pas))
        r+=pas;
  pas/=2;
 }
 out<<fixed<<setprecision(2)<<r;
}
int main()
{
    int i;
    in>>n>>l>>u;
    for(i=1;i<=n;i++)
    in>>cost[i];
    for(i=1;i<=n;i++)
    in>>timp[i];
    cautbin();
    return 0;
}