Cod sursa(job #1568745)

Utilizator Master011Dragos Martac Master011 Data 14 ianuarie 2016 18:02:25
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<cstdio>
using namespace std;

const int nMax = 3e4 + 1, lim = 1e5, bufSize = 5000;

int pos = bufSize, st, dr, n, l, r;
int dq[nMax], c[nMax], tmp[nMax];
double s[nMax];
char buf[bufSize];
FILE *in, *out;

inline char nextch(){
    if(pos == bufSize){
        fread(buf, bufSize, 1, in);
        pos = 0;
    }
    return buf[pos++];
}

inline bool isDigit(char c){
    return (c >= '0' && c <='9');
}

inline int read(){
    int x = 0;
    char ch;

    do{
        ch = nextch();
    }while(!isDigit(ch));

    do{
        x = x * 10 + ch - '0';
        ch = nextch();
    }while(isDigit(ch));

    return x;
}

inline bool verif(double x){
    for(int i = 1 ; i <= n ; ++i){
        s[i] = s[i - 1] + c[i] - tmp[i] * x;
    }

    st = 1; dr = 0;
    for(int i = l ; i <= n ; ++i){
        //push
        while(st <= dr && s[dq[dr]] > s[i - l])
            dr--;
        dq[++dr] = i - l;

        //pop
        if(st <= dr && dq[st] <= i - r)
            st++;

        if(st <= dr && s[i] - s[dq[st]] >= 0)
            return 1;
    }

    return 0;
}

int main (){
    in = fopen("secv3.in","r");
    out = fopen("secv3.out","w");

    n = read(); l = read(); r = read();

    for(int i = 1 ; i <= n ; ++i){
        c[i] = read();
    }

    for(int i = 1 ; i <= n ; ++i){
        tmp[i] = read();
    }

    double rez = 0;
    for(double i = lim ; i > 0.001; i /= 2){
        if(verif(i + rez))
            rez += i;
    }

    fprintf(out,"%.2lf\n", rez);
    return 0;
}