Pagini recente » Cod sursa (job #1513794) | Cod sursa (job #2270559) | Cod sursa (job #249784) | Cod sursa (job #2291132) | Cod sursa (job #971900)
Cod sursa(job #971900)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
#define LE 60666
#include <iomanip>
#define lb long double
lb A[LE];
int deq[LE],i,n,Xs,Ys;
int X[LE],Y[LE];
double dualz(double medium,double value,double timp) {
return value-medium*timp;
}
bool fine(double med) {
for(i=1; i<=n; ++i) A[i]=A[i-1]+dualz(med,X[i],Y[i]);
int st=1,dr=0;
for(i=Xs; i<=n; ++i) {
while (dr>=st&&A[i-Xs]<=A[deq[dr]]) --dr;
deq[++dr]=i-Xs;
while (dr>=st&&i-deq[st]>Ys) ++st;
cout<<deq[st]<<" ";
cout<<A[deq[st]]<<'\n';
if (A[i]-A[deq[st]]>0) return true;
}
return false;
}
double bs() {
double step,pos;
for(step=1; step<=100000; step*=2);
for(pos=0; step>=0.01; step/=2)
if (pos+step<=10000&&fine(pos+step)==true)
pos+=step;
return pos;
}
int main() {
f>>n>>Xs>>Ys;
for(i=1; i<=n; ++i) f>>X[i];
for(i=1; i<=n; ++i) f>>Y[i];
g<<fixed;
g<<setprecision(4);
g<<bs()<<'\n';
f.close();
g.close();
return 0;
}