Pagini recente » Cod sursa (job #1232227) | Cod sursa (job #620488) | Cod sursa (job #923675) | Cod sursa (job #2196572) | Cod sursa (job #1737753)
// fixez x, in cautarea binara, ca fiind suma maxima. daca aleg o secventa, costul ei va fi
// (a1+a2+a3)/(b1+b2+b3). daca o secventa da costul y voi avea (a1+a2+a3)/(b1+b2+b3) = y
// echivalent cu a1+a2+a3 - b1*y-b2*y-b3*y = 0, asadar, pentru x fixat (si pus in loc de y),
// daca gasesc o astfel de relatie pozitiva inseamna ca suma secventei ce o da este >=x
// deci, cu x fixat voi cauta cea mai mare din astfel de expresii, si daca este pozitiva o sa maresc
// x, altfel il scad
#include <fstream>
#define DIM 300010
using namespace std;
int a[DIM], b[DIM], L, U, n, d[DIM], K;
double s[DIM], st, dr, mid;
int pozitiv(double mid) {
s[0] = 0;
for (int i=1;i<=n;i++)
s[i] = s[i-1] + a[i] - b[i] * mid;
int p, u;
u = 0;
p = 1;
for (int i=1;i<=n;i++) {
while (p <= u && s[i] >= s[ d[u] ])
u--;
d[++u] = i;
if (i-d[p] == K)
p++;
if ( i >= L && i+L <= n)
if (s[i+L] - s[ d[p] ] > 0)
return 1;
}
return 0;
}
int main(){
ifstream fin ("secv3.in");
ofstream fout("secv3.out");
fin>>n>>L>>U;
K = U-L;
for (int i=1;i<=n;i++)
fin>>a[i];
for (int i=1;i<=n;i++)
fin>>b[i];
st = 0;dr = 30000000;
while (dr-st >= 0.001) {
mid = (st + dr)/2;
int rez = pozitiv(mid);
if (rez)
st = mid;
else
dr = mid;
}
fout<<st;
return 0;
}