Pagini recente » Cod sursa (job #2791751) | Cod sursa (job #10) | Cod sursa (job #2091377) | Cod sursa (job #1555103) | Cod sursa (job #3216)
Cod sursa(job #3216)
# include <stdio.h>
# include <string.h>
# define maxn 30002
# define maxs 131072
# define _fin "secv3.in"
# define _fout "secv3.out"
# define myint long long
myint c[maxn], t[maxn], l, u, n;
myint sol;
void readf()
{
FILE *fin = fopen(_fin, "r");
myint i;
for (fscanf(fin, "%lld %lld %lld", &n, &l, &u), i=1; i<=n; i++)
fscanf(fin, "%lld", c+i), c[i] *= 100;
for (i=1; i<=n; i++)
fscanf(fin, "%lld", t+i);
fclose(fin);
}
myint deque[maxn], st, dr; // stanga / dreapta cozii
myint aux[maxn];
myint pozsum(myint val)
{
myint i;
for (i=1; i<=n; i++)
aux[i] = aux[i-1] + c[i] - val * t[i];
// inseram in deque primele l-1 elemente
st=1, dr=0;
memset(deque, 0, sizeof(deque));
for (i=1; i<=n; i++)
{
if ( i-l >= 1 )
{
while ( aux[ deque[dr] ] > aux[ i-l ] && dr >= st ) dr--;
deque[ ++dr ] = i-l;
}
if ( i-u-1 >= 1 )
// scoatem elementul din varful listei
if ( deque[ st ] == i-u-1 ) ++st;
if ( aux[ i ] - aux[ deque[ st ] ] >= 0 && i >= l ) return 1;
}
return 0;
}
void solve()
{
myint i, step = maxs;
for (i=0; step; step>>=1)
if ( pozsum(i + step) )
i += step;
sol = i;
}
void writef()
{
double rez = (double) sol / 100.0;
FILE *fout = fopen(_fout, "w");
fprintf(fout, "%.2f\n", rez), fclose(fout);
}
int main()
{
readf();
solve();
writef();
return 0;
}