Cod sursa(job #1259173)

Utilizator Kira96Denis Mita Kira96 Data 9 noiembrie 2014 19:40:16
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<fstream>
//#include<iostream>
#include<cstdio>
#include<map>
#include<set>
#define FIT(a,b) for(vector<int>::iterator a=b.begin();a!=b.end();a++)
#include<stack>
#define ROF(a,b,c) for(long long a=b;a>=c;--a)
#include<vector>
#include<algorithm>
#define FOR(a,b,c) for(long long a=b;a<=c;++a)
#define REP(a,b) for(register int a=0;a<b;++a)
#include<cstring>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<queue>
#define debug cerr<<"OK";
#define pii pair<int,int>
#define f cin
#define g cout
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define eps 1.e-7
#define N 132000
#define M 33000
#define SQ 350
#define mod 666013
using namespace std;
/*ifstream f("a.in");
ofstream g("a.out");*/
/*int dx[]={0,0,1,0,-1};
int dy[]={0,1,0,-1,0};*/
ifstream f("secv3.in");
ofstream g("secv3.out");
deque<int> D;
int n,l,r;
long long sol,st,dr,a[N],b[N],pl[N];
int pula(int x)
{
    FOR(i,1,n)
    {
        pl[i]=a[i]-x*b[i];
        pl[i]+=pl[i-1];
    }
    D.clear();
    FOR(i,l,n)
    {
        while(!D.empty()&&pl[i-l]<pl[D.back()])
            D.pop_back();
        D.pb(i-l);
        if(pl[i]-pl[D.front()]>=0)
        return 1;
        if(D.front()==i-r)
            D.pop_front();
    }
    return 0;
}
int main ()
{
    f>>n>>l>>r;
    FOR(i,1,n)
    {
        f>>a[i];
        a[i]*=100;
    }
    FOR(i,1,n)
    {
        f>>b[i];
    }
    st=0;
    dr=1000000;
    while(st<=dr)
    {
        int mij=(st+dr)>>1;
        if(pula(mij))
            st=mij+1;
        else
            dr=mij-1;
    }
    sol=st-1;
    g<<sol/100<<".";
    sol%=100;
    if(sol<10)
        g<<"0";
    g<<sol;
	return 0;
}
//Look at me! Look at me! The monster inside me has grown this big!