Cod sursa(job #1314236)

Utilizator thesvcoolmanLucian Bicsi thesvcoolman Data 11 ianuarie 2015 17:21:39
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<fstream>
#include<vector>
#include<iomanip>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

struct Elem {
    int c, t;
    Elem(int a, int b) {c = a; t = b;}
    Elem() {}
};
vector<Elem> S;
vector<double> PROF;
int n, l, u;

Elem sum(const Elem &a, const Elem &b) {
    return Elem(a.c+b.c, a.t+b.t);
}
Elem dif(const Elem &a, const Elem &b) {
    return Elem(a.c-b.c, a.t-b.t);
}

double Sum;
Elem E;
double findMax(int m, int M, double K1, double K2) {
    double K = (K1+K2)/2;
    int e = m;
    double Prof = (double)S[m].c/S[m].t - K;
    double Sum = Prof;
    double p;

    for(int i=m+1; i<=M; i++) {
        p = (double)S[i].c/S[i].t - K;
        if(p > Prof){
            Prof = p;
            e = i;
        }
    }
    for(int i=M+1; i<=n; i++) {
        E = dif(S[i], S[i-M]);
        p = (double)E.c/E.t - K;
        if(p > Prof){
            Prof = p;
            e = i;
        }
    }

    for(int b = max(e-M, 0); b<=e-m; b++) {
        E = dif(S[e], S[b]);
        Sum = max(Sum, (double)E.c/E.t - K);
    }

    if(Sum*Sum < 0.001 * 0.001) return K;

    if(Sum > 0) {
        return findMax(m, M, K, K2);
    } else {
        return findMax(m, M, K1, K);
    }
}

int main() {
    fin>>n>>l>>u;
    int c, t;
    S.resize(n+1);
    PROF.resize(n+1, 0);
    S[0].c = S[0].t = 0;
    for(int i=1; i<=n; i++) {
        fin>>S[i].c;
        S[i].c += S[i-1].c;
    }
    for(int i=1; i<=n; i++) {
        fin>>S[i].t;
        S[i].t += S[i-1].t;
    }
    Elem e;

    fout<<setprecision(20)<<findMax(l, u, 0, 1000);
}