Cod sursa(job #553641)

Utilizator zizou_adyIacov Adrian zizou_ady Data 14 martie 2011 10:46:28
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
 
#define MIN -9999999
#define MAX 9999999
 
ifstream fin("secv3.in");
ofstream fout("secv3.out");
 
void Read();
void Solve();
 
int maxim = MIN;
int minim = MAX;
double sol;
vector <int> c;
vector <int> t;
 
deque <int> dmax;
deque <int> dmax2;
deque <int> dmin;
deque <int> dmin2;
 
int n, l, u;
 
int main()
{
    Read();
    Solve();
    fout << sol << '\n';
    fout.close();
    fin.close();
    return 0;
}
 
void Read()
{
    fin >> n >> l >> u;
    t.resize(n+1);
    c.resize(n+1);
    int x;
    for (int i = 1; i <= n; ++i)
    {
        fin >> x;
        c[i] = c[i-1] + x;
    }
    for (int i = 1; i <= n; ++i)
    {
        fin >> x;
        t[i] = t[i-1] + x;
    }
}
 
void Solve()
{
    for (int i = 1; i <= n; ++i)
    {
        while (!dmax.empty() && c[i] >= c[dmax.back()])
        {
            dmax.pop_back();
        }
        dmax.push_back(i);
        while (!dmin.empty() && c[i] <= c[dmin.back()])
        {
            dmin.pop_back();
        }
        dmin.push_back(i);
        while (!dmax.empty() && dmax.front() >= dmin.front())
            if (dmax.size() == 1)
                dmax.clear();
            else
                dmax.pop_front();
        if (i - dmax.front() >= u )
		{
            dmax.pop_front();
			maxim = MIN;
		}
		if (i - dmin.front() >= u )
		{
            dmin.pop_front();
			maxim = MIN;
		}
        if (i >= l && c[dmax.front()] - c[dmin.front()-1] > maxim)
        {
            maxim = c[dmax.front()] - c[dmin.front()-1];
			minim = t[dmax.front()] - t[dmin.front()-1];
        }
		if (sol < (double)maxim/minim)
			sol = (double)maxim/minim;
    }
    if (l == 1)
    {
        if ((double)(c[n]-c[n-1])/(t[n]-t[n-1]) > sol)
            sol = (double)(c[n]-c[n-1])/(t[n]-t[n-1]);
    }
}