Pagini recente » Cod sursa (job #771630) | Cod sursa (job #1698892) | Cod sursa (job #1649566) | Cod sursa (job #2220666) | Cod sursa (job #2892069)
#include <iostream>
#include <fstream>
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 = 100005, 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 << (double) sol / (double) 100;
return 0;
}