Pagini recente » Cod sursa (job #617344) | Cod sursa (job #2746812) | Cod sursa (job #231772) | Cod sursa (job #424898) | Cod sursa (job #2879)
Cod sursa(job #2879)
# include <stdio.h>
# include <string.h>
# define maxn 30002
# define maxs 131072
# define _fin "secv3.in"
# define _fout "secv3.out"
int c[maxn], t[maxn], l, u, n;
int sol;
void readf()
{
FILE *fin = fopen(_fin, "r");
int i;
for (fscanf(fin, "%d %d %d", &n, &l, &u), i=1; i<=n; i++)
fscanf(fin, "%d", c+i), c[i] *= 100;
for (i=1; i<=n; i++)
fscanf(fin, "%d", t+i);
fclose(fin);
}
int deque[maxn], st, dr; // stanga / dreapta cozii
int aux[maxn];
int pozsum(int val)
{
int 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()
{
int i, step = maxs;
for (i=0; step; step>>=1)
if ( pozsum(i + step) )
i += step;
sol = i;
}
void writef()
{
FILE *fout = fopen(_fout, "w");
fprintf(fout, "%d.%d\n", sol/100, sol%100), fclose(fout);
}
int main()
{
readf();
solve();
writef();
return 0;
}