Cod sursa(job #1665529)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 27 martie 2016 00:57:55
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#include <queue>
using namespace std;

const int MAX = 30000;

int a[1 + MAX];
int b[1 + MAX];
long long v[1 + MAX];
int n, l, u;

int ssm()
{
    deque<int> dq;
    long long suma = 0;

    for(int i = 1; i <= n; i++)
    {
        suma = v[i];

        /// pop in dq
        if(!dq.empty() && dq.front() < i - u )
            dq.pop_front();

        /// push in dq
        if(i - l >= 0)
        {
            while(!dq.empty() && v[dq.back()] >= v[i - l])
                dq.pop_back();
            dq.push_back(i - l);
        }

        if(!dq.empty() && suma - v[dq.front()] >= 0)
            return 1;
    }
    return 0;
}

bool verif(int x)
{
    for(int i = 1; i <= n; i++)
        v[i] = a[i] * 100 - b[i] * x + v[i - 1];
    if(ssm() == 1)
        return true;
    return false;
}

int cb()
{
    int i = 0, pas = 1 << 20;
    while(pas)
    {
        if(verif(i + pas) == 1)
            i += pas;
        pas >>= 1;
    }
    return i;
}

int main()
{
    FILE *fin, *fout;

    fin = fopen("secv3.in", "r");
    fout = fopen("secv3.out", "w");

    fscanf(fin, "%d%d%d", &n, &l, &u);

    for(int i = 1; i <= n; i++)
        fscanf(fin, "%d", &a[i]);
    for(int i = 1; i <= n; i++)
        fscanf(fin, "%d", &b[i]);

    fprintf(fout, "%.2f\n", (double) cb() / 100);

    return 0;
}