Cod sursa(job #1537101)

Utilizator algebristulFilip Berila algebristul Data 26 noiembrie 2015 22:05:33
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <deque>

#define FILEIN "secv3.in"
#define FILEOUT "secv3.out"

const int NMAX = 30005;

using namespace std;

int l, u, n;
int c[NMAX];
int t[NMAX];
long long ans;

bool ok(long long x) {
    long long a[NMAX];
    deque<int> d;

    a[0] = 0;

    for (int i = 1; i <= n; i++) {
        a[i] = 1LL * c[i] - 1LL * x * t[i];
        a[i] += a[i-1];
    }

    for (int i = l; i <= n; i++) {
        while (!d.empty()) {
            if (i - d.back() > u)
                d.pop_back();
            else
            if (a[i - l] <= a[d.front()])
                d.pop_front();
            else
                break;
        }

        d.push_front(i - l);
        
        if (a[i] >= a[d.front()])
            return true;
    }

    return false;
}

void solve(long long l, long long r) {
    while (l <= r) {
        long long mid = (l + r)/2;
        if (ok(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    cin >> n >> l >> u;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        c[i] *= 100;
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    solve(1, 3000000000);

    cout << setprecision(2) << fixed << (double)ans/100 << '\n';


    return 0;
}