Cod sursa(job #1755261)

Utilizator silkMarin Dragos silk Data 9 septembrie 2016 17:38:10
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#define NMax 30000
#define INF 1<<30
#define MIN(a,b)((a)<(b)?(a):(b))

int deque[NMax+1];
int t[NMax+1];
int a[NMax+1];
int b[NMax+1];
int N,L,U,K;

bool is_good(int X)
{
    int i,j,inc,sf,ans=-INF;

    for(i = 1; i <= N; ++i) t[i] = t[i-1] + a[i] - X*b[i];

    inc = 0; sf = -1; ans = t[L];
    for(j = L+1, i = 1; i <= K; ++i,++j)
    {
        while( sf>=inc && t[i] <= t[ deque[sf] ] ) --sf;
        deque[++sf] = i;

        if( t[j]-MIN(t[ deque[inc] ],0) > ans ) ans = t[j]-MIN(t[ deque[inc] ],0);
    }

    for(i = K+1, j = U+1; j <= N; ++i,++j)
    {
        if( t[j]-t[ deque[inc] ] > ans ) ans = t[j]-t[ deque[inc] ];

        while( sf>=inc && deque[inc]<=i-K ) ++inc;
        while( sf>=inc && t[i] <= t[ deque[sf] ] ) --sf;
        deque[++sf] = i;
    }

    if(ans>=0) return 1;
    return 0;
}

int main(){
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);

    int i,st,dr,mid,f;

    scanf("%d %d %d",&N,&L,&U);
    for(i = 1; i <= N; ++i) { scanf("%d",&a[i]); a[i]*=100; }
    for(i = 1; i <= N; ++i) scanf("%d",&b[i]);

    K = U-L+1;
    for(st = 1, dr = NMax*100; st <= dr; )
    {
        mid = (st+dr)/2;
        if( is_good(mid) ) { f = mid; st = mid+1; }
        else dr = mid-1;
    }

    printf("%.2f\n",f/100);


return 0;
}