Cod sursa(job #1738385)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 6 august 2016 16:40:45
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<bits/stdc++.h>
#define INF 1<<20
#define maxN 30005
using namespace std;
int n,a[maxN],b[maxN],l,u;
long long s[maxN],mid;
deque<long long> q;
int val(int x)
{
    int i;
    //sume partiale
    for(i=1;i<=n;i++)
        s[i]=s[i-1]+a[i]*100-x*b[i];
    q.clear();
    //min_deque
    for(int i=l;i<=n;i++)
    {
        while(!q.empty() && s[q.back()]>=s[i-l])
            q.pop_back();
        q.push_back(i-l);
        if((i-q.front())==u)
            q.pop_front();
        if((s[i]-s[q.front()])>=0) return 1;
    }
    return 0;
}
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",&a[i]);
    }
    for(int j=1;j<=n;j++)
    {
        scanf("%d",&b[j]);
    }
    long long ls=1;
    long long ld=INF;
    while (ls<=ld)
    {
        mid=ls+(ld-ls)/2;
        if (val(mid)) ls=mid+1;
            else ld=mid-1;
    }
    printf("%.2lf\n",mid/100.0);
    return 0;
}