Cod sursa(job #2243483)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 20 septembrie 2018 18:04:21
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

#define NM 30002

using namespace std;

int n, x, y, d;
double a[NM], b[NM], sa[NM], sb[NM];
double dpa[NM], dpb[NM];
double mx;

int main()
{
    ifstream fin ("secv3.in");
    ofstream fout ("secv3.out");
    fin >> n >> x >> y;
    d = y - x;
    for(int i = 1; i <= n; i++)
    {
        fin >> a[i];
        sa[i] = sa[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i++)
    {
        fin >> b[i];
        sb[i] = sb[i - 1] + b[i];
    }
    for(int i = n - d + 1; i <= n; i++)
        if(dpb[n] == 0 || (sa[n] - sa[i - 1]) / (sb[n] - sb[i - 1]) > dpa[n] / dpb[n])
        {
            dpa[n] = sa[n] - sa[i - 1];
            dpb[n] = sb[n] - sb[i - 1];
        }
    for(int i = n - 1; i >= 1; i--)
    {
        dpa[i] = dpa[i + 1] - a[i + 1];
        dpb[i] = dpb[i + 1] - b[i + 1];
        if(dpb[i] == 0 || dpa[i] / dpb[i] < (sa[i] - sa[i - d]) / (sb[i] - sb[i - d]))
        {
            dpa[i] = sa[i] - sa[i - d];
            dpb[i] = sb[i] - sb[i - d];
        }
    }
    for(int i = x; i <= n; i++)
    {
        double dpa1, dpb1;
        bool ok = (dpa[i - x] >= dpb[i - x]);
        dpa1 = sa[i] - sa[i - x] + ok * dpa[i - x];
        dpb1 = sb[i] - sb[i - x] + ok * dpb[i - x];
        if(dpa1 / dpb1 > mx)
            mx = dpa1 / dpb1;
    }
    fout << fixed << setprecision(15) << mx << "\n";
    return 0;
}