Cod sursa(job #2467869)

Utilizator Vlad.Vlad Cristian Vlad. Data 5 octombrie 2019 09:51:22
Problema Secventa 3 Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <deque>
#include <iostream>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
deque<pair<int,int>> deq;
int a[30001], b[30001], c[30001];
int n, l, u;
void read() {
    fin >> n >> l >> u;
    for (int i = 1; i <= n; ++i) {
        fin >> a[i];
        a[i] = a[i] * 100;
    }
    for (int i = 1; i <= n; ++i) {
        fin >> b[i];
        b[i] = b[i];
    }
}
long long maxRatio(int k) {
    for (int i = 1; i <= n; ++i) {
        c[i] = c[i - 1] + a[i] - k * b[i];
    }
    long long maxSum = -9999999999999999;
    for (int i = l; i <= n; ++i) {
        while (!deq.empty() && deq.back().first > c[i - l]) {
            deq.pop_back();
        }
        deq.emplace_back(c[i - l], i - l);
        if (c[i] - deq.front().first > maxSum) {
            maxSum = c[i] - deq.front().first;
        }
        if (deq.front().second == i - u) {
            deq.pop_front();
        }
    }
    deq.clear();
    return maxSum;
}
int main()
{
    read();
    int st, dr, mi;
    st = 0;
    dr = 100000;
    while (dr - st > 1) {
        mi = (st + dr) / 2;
        if (maxRatio(mi) < 0) {
            dr = mi;
        }
        else
            st = mi;
    }
    if (maxRatio(st) >= 0)
        fout << st / 100.0 << "\n";
    else
        fout << dr / 100.0 << "\n";
    return 0;
}