Cod sursa(job #2058198)

Utilizator robertispasIspas Robert robertispas Data 5 noiembrie 2017 11:47:20
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iomanip>
#include <fstream>

using namespace std;

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

int n, d[100001], st=0, dr=-1, l, u;
float mx=-100001, v[1000001], x[100001];

int main()
{
    in>>n>>l>>u;
    for(int i = 1; i <= n; i++)
    {
        in>>v[i];
        v[i] += v[i-1];
    }
    for(int i = 1; i <= n; i++)
    {
        in>>x[i];
        x[i] += x[i-1];
    }
    for(int i = l; i <= n; i++)
    {
        if(st <= dr && d[st] == i - u - 1)
        {
            st++;
        }
        while(st <= dr && (v[i] - v[i-l])/(x[i] - x[i-l]) >= (v[i] - v[d[dr]])/(x[i] - x[d[dr]]))
        {
            dr--;
        }
        d[++dr] = i - l;
        if(mx < (v[i] - v[d[st]])/(x[i]-x[d[st]]))
            mx=(v[i]-v[d[st]])/(x[i]-x[d[st]]);
    }
    out<<setprecision(2)<<fixed<<mx;
    return 0;
}