Cod sursa(job #1630152)

Utilizator usermeBogdan Cretu userme Data 4 martie 2016 22:45:20
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <deque>

using namespace std;

struct ap{
    double x;
    int y;
};

deque<ap> d;

int n, l, u;

int a[30001], b[30001];

FILE* f = fopen("secv3.in", "r");
FILE* h = fopen("secv3.out", "w");

int main() {
    fscanf(f, "%d%d%d", &n, &l, &u);
    for (int i = 1; i <= n; ++i) {
        fscanf(f, "%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        fscanf(f, "%d", &b[i]);
    }
    double st = 0, dr = 1000;
    while (dr - st > 0.0001) {
        double mid = (st + dr) / 2;
        double rez[30001];
        rez[0] = 0;
        for (int i = 1; i <= n; ++i) {
            rez[i] = a[i] - (double)b[i] * mid;
            rez[i] += rez[i - 1];
        }
        double smax = -1000;
        for (int i = 0; i <= n; ++i) {
            if (i >= l) {
                while(!d.empty() && d.back().x > rez[i - l]) {
                    d.pop_back();
                }
                d.push_back({rez[i - l], i});
                if (!d.empty() && i - d.front().y > u) {
                    d.pop_front();
                }
                if (rez[i] - d.front().x > smax) {
                    smax = rez[i] - d.front().x;
                }
            }
        }
        if (smax > 0) {
            st = mid;
        } else {
            dr = mid;
        }
        d.clear();
    }
    fprintf(h, "%.4lf", st);
    return 0;
}