Cod sursa(job #971900)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 10 iulie 2013 15:11:01
Problema Secventa 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");

#define LE 60666
#include <iomanip>
#define lb long double

lb A[LE];
int deq[LE],i,n,Xs,Ys;
int X[LE],Y[LE];

double dualz(double medium,double value,double timp) {
    return value-medium*timp;
}

bool fine(double med) {
    for(i=1; i<=n; ++i) A[i]=A[i-1]+dualz(med,X[i],Y[i]);

    int st=1,dr=0;

    for(i=Xs; i<=n; ++i) {
        while (dr>=st&&A[i-Xs]<=A[deq[dr]]) --dr;
        deq[++dr]=i-Xs;
        while (dr>=st&&i-deq[st]>Ys) ++st;
        cout<<deq[st]<<" ";
        cout<<A[deq[st]]<<'\n';

        if (A[i]-A[deq[st]]>0) return true;
    }
    return false;
}

double bs() {
    double step,pos;
    for(step=1; step<=100000; step*=2);

    for(pos=0; step>=0.01; step/=2)
        if (pos+step<=10000&&fine(pos+step)==true)
            pos+=step;
    return pos;
}
int main() {
    f>>n>>Xs>>Ys;
    for(i=1; i<=n; ++i) f>>X[i];
    for(i=1; i<=n; ++i) f>>Y[i];


    g<<fixed;
    g<<setprecision(4);
    g<<bs()<<'\n';



    f.close();
    g.close();
    return 0;
}