Pagini recente » Cod sursa (job #657920) | Cod sursa (job #2074015) | Cod sursa (job #200986) | Cod sursa (job #2230085) | Cod sursa (job #1393189)
#include <fstream>
#include <iomanip>
#define NMax 30010
#define INF 1<<31-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)
{
for (int i=1; i<=n; i++)
newSeq[i] = newSeq[i-1] + 1LL * s[i].c * 100 - s[i].t * div;
long long sMax = -INF;
fr=0;
ba=0;
for (int i=1; i<=n; i++) {
while (newSeq[i] <= newSeq[deq[fr]] && ba <= fr)
fr--;
while (i - deq[ba] > u && ba <= fr)
ba++;
long long stmp = newSeq[i] - newSeq[deq[ba]];
deq[++fr] = i;
if (i - deq[ba] + 1 >= l && sMax < stmp)
sMax = stmp;
}
if (sMax >= 0)
return true;
return false;
}
int main()
{
f>>n>>u>>l;
for (int i=1; i<=n; i++)
f>>s[i].c;
for (int i=1; i<=n; i++)
f>>s[i].t;
lt = 1;
rt = 30000000000;
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;
}