Pagini recente » Cod sursa (job #99373) | Cod sursa (job #461899) | Cod sursa (job #36454) | Cod sursa (job #1450421) | Cod sursa (job #332288)
Cod sursa(job #332288)
#include <cstdio>
#define Nmax 30010
int n, a, b, i, Sum, p, u, st, mij, dr, sol, j;
int v[Nmax], d[Nmax], c[Nmax], t[Nmax];
int cont (int X) {
Sum = 0; v[1] = 0;
for (i = 1; i <= n; i++)
v[i + 1] = c[i] -X * t[i];
for(i = 1; i <= n + 1; i++)
v[i]+= v[i-1];
Sum = v[a + 1];
p = u = 1; d[1] = 1;
for (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 () {
FILE *f = fopen ("secv3.in", "r");
FILE *g = fopen ("secv3.out", "w");
fscanf (f, "%d %d %d", &n, &a, &b);
for (i = 1; i <= n; i++){
fscanf (f, "%d", &c[i]), c[i]*= 100;
dr+= c[i];
}
for (i = 1; i <= n; i++)
fscanf (f, "%d", &t[i]);
while (st <= dr) {
mij = (st + dr) >> 1;
if( cont(mij) ) {
sol = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
fprintf (g, "%.2lf", (double)sol / (double)100);
fclose (f);
fclose (g);
return 0;
}