Cod sursa(job #2892074)

Utilizator ClaudiuChelceaClaudiuChelcea ClaudiuChelcea Data 20 aprilie 2022 17:34:16
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <iomanip>

int cont (int idx, int n, int array1[], int array2[], int a, int b) {
	
    // Variables
    int v[30000], d[30000];
    int p = 1, sum = 0, u = 1;

	v[1] = 0;
	for (int i = 1; i <= n; i++) {
		v[i + 1] = v[i] + array1[i] - idx * array2[i];
    }
 
	sum = v[a + 1];
	d[1] = 1;
	for (int i = 2; i + a <= n + 1; i++) {
		
		while (p <= u && i+a - b > d[p]) {
            p++;
        }
		while (p <= u && v[i] <= v[ d[u] ]) {
            u--;
        }
		d[++u] = i;
		
		if( v[i+a] - v[d[p]] >= sum) {
            sum = v[i+a] - v[d[p]];
        } 
	}
	
	if (sum >= 0) return 1;
	return 0;
}
 
int main (void)
{
    // Deschide fisiere
    std::ifstream fin ("secv3.in");
    std::ofstream fout ("secv3.out");

    // Variables
    int n {0}, a {0}, b {0};
    int array1[30000], array2[30000];
	
    // Read data
    fin >> n >> a >> b;
	for (int i = 1; i <= n; i++){
        fin >> array1[i];
        array1[i] = array1[i] * 100;
	}
	
	for (int i = 1; i <= n; i++) {
		fin >> array2[i];
    }

	int right = 100010, left = 0, sol = 0, middle = 0;
	while (left <= right) {
		middle = (left + right) / 2;
		
		if(cont(middle, n, array1, array2, a, b)) {
			sol = middle;
			left = middle + 1;
		} else {
			right = middle - 1;
        }
    }
	
    fout << std::setprecision(2) << (double) sol / (double) 100 << std::endl;
	
	return 0;
}