Cod sursa(job #1520210)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 8 noiembrie 2015 15:00:42
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

const int NMAX=30005;

int n,L,U,deq[NMAX];
double sol;
long long s[NMAX],t[NMAX],rez[NMAX];
//pot face problema pe int deoarece inecuatia >= o pot inmulti cu 10^2
//si cautarea binara pe inturi va fi defapt cautare binara pe double:)

int main()
{
    int i,j,pr,ul,x,ok;
    long long kkt,st,mij,dr;
    fin>>n>>L>>U;
    for (i=1;i<=n;i++)
    {
        fin>>x;
        x*=100;
        s[i]=s[i-1]+x;
    }
    for (i=1;i<=n;i++) fin>>x,t[i]=t[i-1]+x;

    st=1;dr=3000000000;//rasp max initial*100
    while (st<=dr)
    {
        mij=(st+dr)/2;
        for (i=1;i<=n;i++) rez[i]=s[i]-1LL*mij*t[i];
        pr=1;ul=ok=0;
        for (i=L;i<=n;i++)
        {
            //pun rez[i-L]
            while (ul>=pr && rez[deq[ul]]>=rez[i-L]) ul--;
            deq[++ul]=i-L;
            //scot pr daca e nevoie
            if (deq[pr]<(i-U)) pr++;
            if (rez[i]>=rez[deq[pr]]) ok=1;
        }

        if (ok==1)
        {
            sol=mij;
            st=mij+1;
        }
        else dr=mij-1;
    }
    sol/=100.0;
    fout<<setprecision(3)<<fixed;
    fout<<sol<<"\n";
    return 0;
}