Cod sursa(job #2297846)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 6 decembrie 2018 18:36:49
Problema Secventa 3 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <deque>

using namespace std;

const float eps = 0.001;

bool secvZero(vector<float> v, int mn, int mx)
{
    for(int i = 1; i < v.size(); ++i)
        v[i] += v[i-1];
    deque<int> d;
    for(int i = 0; i < mn; ++i)
        d.push_front(i);
    if(v[mn-1] >= 0)
        return true;
    for(int i = mn; i < v.size(); ++i)
    {
        while(d.empty() == false && v[d.front()] > v[i-mn])
            d.pop_front();
        d.push_front(i-mn);
        if(d.back() <= i-mx)
            d.pop_back();
        if(v[i] - v[d.back()] >= 0)
            return true;
    }
    return false;
}

int main()
{
    ifstream in("secv3.in");
    int n, mn, mx;
    in >> n >> mn >> mx;
    vector<int> cost(n), timp(n);
    for(int i = 0; i < n; ++i)
        in >> cost[i];
    for(int i = 0; i < n; ++i)
        in >> timp[i];
    in.close();

    float rasp = 0;
    float st = 0, dr = 1000, mid;
    vector<float> v(n);
    while(dr - st > eps)
    {
        mid = (st + dr) / 2;
        for(int i = 0; i < n; ++i)
            v[i] = cost[i] - mid * timp[i];
        if(secvZero(v, mn, mx))
        {
            rasp = max(rasp, mid);
            st = mid;
        }
        else
            dr = mid;
    }

    ofstream out("secv3.out");
    out << fixed << setprecision(2) << rasp;
    out.close();
    return 0;
}