Pagini recente » Monitorul de evaluare | Cod sursa (job #996690) | Cod sursa (job #1206788) | Cod sursa (job #2072587) | Cod sursa (job #1560250)
#include <stdio.h>
#define MAXN 30000
int c[MAXN], t[MAXN], dq[MAXN];
double sum[MAXN];
inline char bun(double x, int n, int l, int r){
int i, st = 0, dr = 1;
dq[0] = 0;
sum[0] = c[0] - x * t[0];
if(l == 1 && sum[0] >= 0)
return 1;
for(i = 1; i < n; i++){
sum[i] = sum[i - 1] + c[i] - x * t[i];
if(i - dq[st] + 1 > r)
st++;
if(sum[i] - sum[dq[st]] >= 0)
return 1;
while(dr > st && sum[i] < sum[dq[dr - 1]])
dr--;
dq[dr] = i;
dr++;
}
return 0;
}
int main(){
FILE *in = fopen("secv3.in", "r");
int n, l, r, i;
fscanf(in, "%d%d%d", &n, &l, &r);
for(i = 0; i < n; i++)
fscanf(in, "%d", &c[i]);
for(i = 0; i < n; i++)
fscanf(in, "%d", &t[i]);
fclose(in);
double rez = 0, pas;
for(pas = (double)(1 << 9); pas > 0.001; pas /= 2){
if(bun(rez + pas, n, l, r))
rez += pas;
}
FILE *out = fopen("secv3.out", "w");
fprintf(out, "%.2lf", rez);
fclose(out);
return 0;
}