Cod sursa(job #1259165)

Utilizator Kira96Denis Mita Kira96 Data 9 noiembrie 2014 19:29:10
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 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 sol,n,l,r,a[N],b[N],A[N],B[N],S[N];
int main ()
{
    f>>n>>l>>r;
    FOR(i,1,n)
    {
        f>>a[i];
        a[i]*=100;
    }
    FOR(i,1,n)
    {
        f>>b[i];
    }
    FOR(i,1,n)
    {
        A[i]=A[i-1]+a[i];
        B[i]=B[i-1]+b[i];
        S[i]=A[i]/B[i];
    }
    FOR(i,l,n)
    {
        while(!D.empty()&&S[D.back()]<S[i-l])
            D.pop_back();
        D.pb(i-l);
        int k=D.front();
        if((A[i]-A[k])/(B[i]-B[k])>sol)
            sol=(A[i]-A[k])/(B[i]-B[k]);
        if(D.front()==i-r)
            D.pop_front();
    }
    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!