Cod sursa(job #3338271)

Utilizator parus_majorParus Major parus_major Data 2 februarie 2026 01:41:43
Problema Secventa 3 Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

const int MAXN = 30002;

double C[MAXN], T[MAXN], Val[MAXN];
int Deque[MAXN];
int N, L, U;

bool verif(double B) {
    int front = 1;
    int back = 0;
    Val[0] = 0.0;
    for (int i = 1; i <= N; ++i) {
        Val[i] = C[i] - B * T[i];
        
        // pop i - U
        if (front <= back && Deque[front] <= i - U) {
            ++front;
        }

        // push i - L
        if (i >= L) {
            while (front <= back && Val[i - L] <= Val[Deque[back]]) --back;
            Deque[++back] = i - L;
        }

        if (front <= back && Val[Deque[front]] <= Val[i]) return true;
    }

    return false;
}

int main()
{
    fin >> N >> L >> U;
    for (int i = 1; i <= N; ++i) {
        fin >> C[i];
        C[i] += C[i - 1];
    }
    for (int i = 1; i <= N; ++i) {
        fin >> T[i];
        T[i] += T[i - 1];
    }

    double sol = 0.0;
    for (double v = 1.0; v >= 0.01; v /= 2.0) {
        if (verif(sol + v)) sol += v;
    }

    fout << fixed << setprecision(2) << sol;
    return 0;
}

// ( C[i] - C[j] ) / (T[i] - T[j]) >= B
// C[i] - C[j] >= B (T[i] - T[j])
// C[i] - B * T[i] >= C[j] - B * T[j]