Pagini recente » Cod sursa (job #1690712) | Cod sursa (job #2729537) | Cod sursa (job #179094) | Cod sursa (job #1253898) | Cod sursa (job #1393358)
#include <fstream>
#include <iomanip>
#include <string.h>
#define NMax 30010
#define INF 1LL<<62-1
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int n, l, u, deq[NMax], ba, fr;
long long newSeq[NMax], lt, mid, rt, sol;
struct secventa
{
int c;
int t;
}s[NMax];
long long checkSum(long long div)
{
memset(deq, 0, sizeof (deq));
for (int i=1; i<=n; i++)
newSeq[i] = newSeq[i-1] + 1LL * s[i].c * 100 - 1LL*s[i].t * div;
long long sMax = -INF;
fr=0;
ba=0;
for (int i = l; i<=n; i++) {
while (i - deq[ba] > u && ba <= fr)
ba++;
while (newSeq[i-l] <= newSeq[deq[fr]] && ba <= fr)
fr--;
deq[++fr] = i-l;
long long 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 = 3000000000;
while (lt <= rt) {
mid = (lt + rt) / 2;
if (checkSum(mid)) {
lt = mid + 1;
sol = mid;
}
else
rt = mid - 1;
}
g<<setprecision(2)<<fixed<<(double)sol/100;
return 0;
}