Cod sursa(job #1771628)

Utilizator ade_tomiEnache Adelina ade_tomi Data 5 octombrie 2016 20:23:23
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <queue>
#define eps 0.001
#define NMAX 30003
#define DB 1
using namespace std;
deque <int> q;
double d[NMAX], sol;
int a[NMAX], b[NMAX], n, l, u;
int check (double r)
{
    for (int i = 1; i <= n; i++)
        d[i] = (double) d[i - 1] +  a[i] - b[i] * r;
   
   
    for (int i = l; i <= n; i++)
    {
        if (!q.empty() && q.front() == i - u - 1)
            q.pop_front();
        while (!q.empty() && d[i - l + 1] < d[q.back()])
            q.pop_back();
        q.push_back(i - l + 1);
        if (d[i] - d[q.front()] > 0){
            if(DB)
            {
                cout << d[i] - d[q.front()] << " " << i << " " << q.front() << " \n";
            }
            q.clear();
            
            return 1;
        }
    }
    q.clear();
    return 0;
}
int main ()
{
    ifstream cin ("secv3.in");
    ofstream cout ("secv3.out");
    cin >> n >> l >> u;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    double l1 = 0, l2 = 300003;
    while (l2 - l1 >= eps)
    {
        double mid = (l1 + l2) / 2.0;
        //cout << mid << "\n";
        if (check(mid)){
            l1 = mid ;
            sol = mid;
        }
        else 
            l2 = mid;
    }
    cout <<  sol;
}