Pagini recente » Cod sursa (job #2348883) | Cod sursa (job #1829771) | Cod sursa (job #549705) | Cod sursa (job #2043062) | Cod sursa (job #1609402)
#include <fstream>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int i, n, L, U,D[30100], c[30100], t[30100];
double s[30100], st, dr, mid, sol;
int secv(double S)
{
int st, dr;
for (int i = 1; i <= n; i++)
s[i] = s[i-1]+ c[i] - S*t[i];
st = 1;
dr = 0;
for(int i = L; i <= n; i ++)
{
while (st <= dr && s[i - L] <= s[D[dr]])
dr--;
D[++dr] = i - L;
if (i - U - 1 == D[st] )
st++;
if (s[i] - s[D[st]] > 0)
return 1;
}
return 0;
}
int main()
{
f>>n>>L>>U;
for (i = 1; i <= n; i++)
f>>c[i];
for (i = 1; i <= n; i++)
f>>t[i];
st = 0;
dr = 2000000000;
while (st <= dr)
{
mid = (st + dr) / 2;
if (secv(mid))
{
sol = st;
st = mid + 0.001;
}
else
dr = mid - 0.001;
}
g << sol;
return 0;
}