Cod sursa(job #2458231)

Utilizator Vlad.Vlad Cristian Vlad. Data 19 septembrie 2019 22:13:13
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 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] + a[i - 1];
    }
    for (int i = 1; i <= n; ++i) {
        fin >> b[i];
        b[i] = b[i] + b[i - 1];
    }
}
int maxRatio(int k) {
    for (int i = 1; i <= n; ++i) {
        c[i] = a[i] * 100 - k * b[i];
    }
    int maxSum = -99999999;
    for (int i = 0; i <= n; ++i) {
        while (!deq.empty() && deq.back().first > c[i]) {
            deq.pop_back();
        }
        deq.emplace_back(c[i], i);
        if (i - deq.front().second == u + 1) {
            deq.pop_front();
        }
        if (deq.back().second - deq.front().second >= l) {
            if (deq.back().first - deq.front().first > maxSum) {
                maxSum = deq.back().first - deq.front().first;
            }
        }
    }
    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;
}