Pagini recente » Cod sursa (job #2403978) | Cod sursa (job #266348) | Cod sursa (job #1487368) | Cod sursa (job #1827984) | Cod sursa (job #1393315)
#include <fstream>
#include <iomanip>
#define NMax 30010
#define INF 1LL<<31-1
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int n, l, u, deq[NMax], ba, fr;
double newSeq[NMax], lt, mid, rt, sol;
struct secventa
{
int c;
int t;
}s[NMax];
bool checkSum(double div)
{
for (int i=1; i<=n; i++)
newSeq[i] = newSeq[i-1] + 1.0 * s[i].c - 1.0 * s[i].t * div;
double sMax = -INF;
fr=0;
ba=0;
for (int i=1; i<=n; i++) {
while (newSeq[i] <= newSeq[deq[fr]] && ba <= fr)
fr--;
deq[++fr] = i;
while (i - deq[ba] > u && ba <= fr)
ba++;
double stmp = newSeq[i] - newSeq[deq[ba]];
if (i - deq[ba] >= l && sMax < stmp)
sMax = stmp;
}
if (sMax >= 0)
return true;
return false;
}
int main()
{
f>>n>>l>>u;
for (int i=1; i<=n; i++)
f>>s[i].c;
for (int i=1; i<=n; i++)
f>>s[i].t;
lt = 0;
rt = 30000000;
while (lt <= rt) {
mid = (lt + rt) / 2;
if (checkSum(mid)) {
lt = mid + 0.01;
sol = mid;
}
else
rt = mid - 0.01;
}
g<<setprecision(2)<<fixed<<(double)sol;
return 0;
}