Cod sursa(job #1864738)

Utilizator OlivianOlivian Dan Cretu Olivian Data 31 ianuarie 2017 22:49:32
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<cstdio>
#include<algorithm>
#include<deque>
using namespace std;
const double inf=1e7;
int n,l,u;
int c[30007],t[30007];
double sum2(double vl)
{
    double s[30007],v[30007];
    s[0]=0;
    deque<int> dq;
    double maxi=-30000000;
    for(int i=1;i<=n;i++) {(v[i]=c[i]-(vl*t[i]));s[i]=s[i-1]+v[i];}
    for(int i=l;i<=n;i++)
    {
        while(!dq.empty() && s[i-l]<=s[dq.back()]) dq.pop_back();
        dq.push_back(i-l);
        if(dq.front()<i-u) dq.pop_front();
        maxi=max(maxi,s[i]-s[dq.front()]);
    }
    return maxi;
}
double caut()
{
    double st=0,dr=300007;
    for(int i=1;i<=40;i++)
    {
        double mid=(st+dr)/2;
        if(sum2(mid)>0) st=mid;
        else dr=mid;
    }
    return dr;
}
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d%d%d",&n,&l,&u);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1;i<=n;i++) scanf("%d",&t[i]);
    printf("%.2f",caut());
}