Cod sursa(job #505077)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 30 noiembrie 2010 17:08:10
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#define FIN "secv3.in"
#define FOUT "secv3.out"
#define NMAX 30000
#define VAL 10000

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;
}