Pagini recente » Cod sursa (job #42651) | Cod sursa (job #189580) | Cod sursa (job #1206741) | Cod sursa (job #128077) | Cod sursa (job #332321)
Cod sursa(job #332321)
#include <cstdio>
#define Nmax 30010
int n, a, b, i, p, u, st, mij, dr, sol, j;
int d[Nmax], c[Nmax], t[Nmax];
long long v[Nmax], Sum;
int cont (int X) {
v[1] = 0;
for (i = 1; i <= n; i++)
v[i + 1] = v[i] + (long long)c[i] - (long long)X * (long long)t[i];
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;
}
for (i = 1; i <= n; i++)
fscanf (f, "%d", &t[i]);
dr = 1000 * 100 +10;
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;
}