Pagini recente » Cod sursa (job #3196941) | Cod sursa (job #2949292) | Cod sursa (job #11594) | Cod sursa (job #2824793) | Cod sursa (job #505078)
Cod sursa(job #505078)
#include<stdio.h>
#define FIN "secv3.in"
#define FOUT "secv3.out"
#define NMAX 30000
#define VAL 30001
int K,N,L,U,lg,sol;
int C[NMAX],T[NMAX],DEQUE[NMAX];
long long TMP[NMAX],S[NMAX];
int main()
{
freopen(FIN , "r" , stdin);
freopen(FOUT , "w" , stdout);
scanf("%d %d %d",&N,&L,&U);
for(int i = 1 ; i <= N ; ++i) scanf("%d",&C[i]);
for(int i = 1 ; i <= N ; ++i) scanf("%d",&T[i]);
for(lg = 1 ; lg <= VAL ; lg <<= 1);
for(sol = 0 ; lg ; lg >>= 1)
if(lg + sol < VAL)
{
K = lg + sol;
for(int j = 1 ; j <= N ; ++j)
TMP[j] = 100*(long long)C[j] - K * T[j];
S[0] = 0;
for(int j = 1 ; j <= N ; ++j)
S[j] = S[j - 1] + TMP[j];
int front = 0 , back = 0;
DEQUE[back] = 0;
long long REZ = -VAL;REZ = -VAL;
for(int j = 1 ; j <= N - L ; ++j)
{
while(front <= back && S[DEQUE[back]] >= S[j]) back--;
DEQUE[++back] = j;
while(front <= back && j - DEQUE[front] > U - L) ++front;
if(REZ < S[j + L] - S[DEQUE[front]]) REZ = S[j + L] - S[DEQUE[front]];
}
if( REZ >= 0 ) sol = sol + lg;
}
printf("%.2lf",sol/100.0);
return 0;
}