Cod sursa(job #1248363)

Utilizator tudormaximTudor Maxim tudormaxim Data 24 octombrie 2014 23:25:11
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#define nmax 30005
using namespace std;
struct DEQUE{long double v; long pos;} deq[nmax];
long n,i,l,u,j,c[nmax],t[nmax],op,mop,di,dj,dist;
long double left,right,mij,s[nmax],minim[nmax];
inline int CHECK(long double x){
    di = 1; dj = 0;
    for(long i=1;i<=n;i++) {
        s[i] = (long double)c[i] - x*t[i] + s[i-1];
        while((di<=dj)&&(deq[dj].v >= s[i])) dj--;
        deq[++dj].v = s[i]; deq[dj].pos = i;
        while(deq[di].pos <= i - dist) di++;
        minim[i] = deq[di].v;
        if(i >= l) {
            if(s[i] - minim[i-l] >= 0)
                return 1;
        }
    }
    return 0;
}
int main(){
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    scanf("%ld %ld %ld\n",&n,&l,&u);
    for(i=1;i<=n;i++) scanf("%ld ",&c[i]);
    for(i=1;i<=n;i++) scanf("%ld ",&t[i]);
    left = 0, right = 1000, mop = 20, op = 0, dist = u-l+1;
    do {
        mij = (left + right)/2; op++;
        if (CHECK(mij)) left = mij;
        else right = mij;
    } while (op < mop);
    left = (left+right)/2;
    printf("%.2lf\n",(double)left);
    return 0;
    fclose(stdin);
    fclose(stdout);
}