Cod sursa(job #1393219)

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

#define NMax 30010
#define INF 1ll<<62-1

using namespace std;

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

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

long long checkSum(long long div)
{

    for (int i=1; i<=n; i++)
        newSeq[i] = newSeq[i-1] + 1LL * s[i].c * 100 - 1ll*s[i].t * div;

    long long sMax = -INF;

    fr=0;
    ba=0;

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


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

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

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

        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 = 1;
    rt = 30000000000;

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

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