Cod sursa(job #1393315)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 19 martie 2015 11:53:09
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <iomanip>

#define NMax 30010
#define INF 1LL<<31-1

using namespace std;

ifstream f("secv3.in");
ofstream g("secv3.out");

int n, l, u, deq[NMax], ba, fr;
double newSeq[NMax], lt, mid, rt, sol;
struct secventa
{
    int c;
    int t;
}s[NMax];

bool checkSum(double div)
{

    for (int i=1; i<=n; i++)
        newSeq[i] = newSeq[i-1] + 1.0 * s[i].c - 1.0 * s[i].t * div;
    double sMax = -INF;

    fr=0;
    ba=0;

    for (int i=1; i<=n; i++) {

   while (newSeq[i] <= newSeq[deq[fr]] && ba <= fr)
            fr--;
        deq[++fr] = i;


        while (i - deq[ba] > u && ba <= fr)
            ba++;

        double stmp = newSeq[i] - newSeq[deq[ba]];


        if (i - deq[ba] >= l && sMax < stmp)
            sMax = stmp;

    }

    if (sMax >= 0)
        return true;
    return false;
}

int main()
{
    f>>n>>l>>u;
    for (int i=1; i<=n; i++)
        f>>s[i].c;
    for (int i=1; i<=n; i++)
        f>>s[i].t;

    lt = 0;
    rt = 30000000;

    while (lt <= rt) {
        mid = (lt + rt) / 2;
        if (checkSum(mid)) {
            lt = mid + 0.01;
            sol = mid;
        }
        else
            rt = mid - 0.01;
    }

    g<<setprecision(2)<<fixed<<(double)sol;
    return 0;
}