Pagini recente » Cod sursa (job #1703440) | Cod sursa (job #2315418) | Cod sursa (job #193469) | Profil norisgalan | Cod sursa (job #2892076)
#include <iostream>
#include <fstream>
#include <iomanip>
int cont (int idx, int n, int array1[], int array2[], int a, int b) {
// Variables
int v[30010], d[30010];
int p = 1, sum = 0, u = 1;
v[1] = 0;
for (int i = 1; i <= n; i++) {
v[i + 1] = v[i] + (long long) array1[i] - (long long) idx * (long long) 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[30010], array2[30010];
// 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;
}