Cod sursa(job #2770493)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 21 august 2021 13:19:03
Problema Secventa 3 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
 
using namespace std;
 
long long c[30005], t[30005], s[30005];
int n, l, u;
 
bool ok(int val) {
    deque<int> d;
    d.push_front(1);
    for(int i = 1;i <= n;i ++)
        s[i] = c[i] - 1LL * val * t[i];
    for(int i = l;i <= n; i ++) {
        if(!d.empty() && d.front() == i - u - 1)
            d.pop_front();
        while(!d.empty() && s[d.back()] > s[i - l + 1])
            d.pop_back();
        d.push_back(i - l + 1);
        if(s[i] - s[d.front()] > 0)
            return 1;
    }
    return 0;
}
 
int main() 
{
	ifstream cin ("secv3.in");
	ofstream cout ("secv3.out");
	cin >> n >> l >> u;
    for(int i = 1; i <= n; i ++) {
		cin >> c[i];
        c[i] += c[i-1];
    }
    for(int i = 1; i <= n; i ++)
        c[i] *= 100;
    for(int i = 1; i <= n; i ++) {
		cin >> t[i];
        t[i] += t[i-1];
    }
    int ans = 0;
    for(int step = 1 << 16; step > 0; step >>= 1)
        if(ok((ans + step)))
            ans += step;
    cout << ans / 100 << "." << ans % 100;
    return 0;
}