Cod sursa(job #953859)

Utilizator dariusdariusMarian Darius dariusdarius Data 27 mai 2013 17:46:04
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#include<deque>
using namespace std;
int n,x,y,a[30005],b[30005];
int d[30005];
deque<int> q;
inline bool ok(int p)
{
    int i;
    for(i=1;i<=n;i++)
        d[i]=d[i-1]+a[i]-p*b[i];
    q.clear();
    for(i=x;i<=n;i++)
    {
        while(!q.empty() && d[q.back()]>=d[i-x+1])
            q.pop_back();
        q.push_back(i-x+1);
        if(i-q.front()==y+1)
            q.pop_front();
        if(d[i]>d[q.front()])
            return true;
    }
    return false;
}
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    int i;
    scanf("%d%d%d",&n,&x,&y);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]),a[i]=a[i]*100;
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    int ans=0;
    for(int pas=1<<16;pas;pas>>=1)
        if(ok(ans+pas))
            ans+=pas;
    printf("%d.",ans/100);
    if(ans%100<10)
        printf("0");
    printf("%d\n",ans%100);
    return 0;
}