Pagini recente » Cod sursa (job #3307527) | Cod sursa (job #1918544) | Cod sursa (job #2679341) | Cod sursa (job #341239) | Cod sursa (job #3316439)
#include <stdio.h>
#include <deque>
#include <math.h>
FILE* fin;
FILE* fout;
const int MAX_N = 30'000;
const double EPS = 1e-3;
const int MAX_C = 1'000;
int n, l, r;
int c[MAX_N + 1], t[MAX_N + 1];
double get_value(int idx, double mid) {
return c[idx] - mid * t[idx];
}
bool check(double mid) {
std::deque<double> dq;
for(int i = l; i <= n; i++) {
if(!dq.empty() && i - r >= 0 &&
abs(dq.front() - get_value(i - r, mid)) < EPS) {
dq.pop_front();
}
double x = get_value(i - l, mid);
while(!dq.empty() && dq.back() > x) {
dq.pop_back();
}
dq.push_back(x);
double val = get_value(i, mid);
if(dq.front() <= val) {
return true;
}
}
return false;
}
int main() {
fin = fopen("secv3.in", "r");
fout = fopen("secv3.out", "w");
fscanf(fin, "%d%d%d", &n, &l, &r);
for(int i = 1; i <= n; i++) {
fscanf(fin, "%d", &c[i]);
c[i] += c[i - 1];
}
for(int i = 1; i <= n; i++) {
fscanf(fin, "%d", &t[i]);
t[i] += t[i - 1];
}
double st = 0;
double dr = MAX_C + EPS;
while(dr - st > EPS) {
double mij = (st + dr) / 2;
if(check(mij)) {
st = mij;
} else {
dr = mij;
}
}
fprintf(fout, "%.2lf\n", st);
fclose(fin);
fclose(fout);
return 0;
}