Cod sursa(job #1846756)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 14 ianuarie 2017 00:14:58
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<stdio.h>
#include<deque>

using namespace std;

FILE *in, *out;

const int MAXN = 30004;

struct opt
{
    int c, t;
};


opt v[MAXN], sum[MAXN];
double parti[MAXN];
deque <int> sw;

int n, a, b;

bool merji(double d)
{

    //printf("%lf \n", d);
    parti[0] = 0;
    for(int i = 1; i <= n; i++) {
        parti[i] = sum[i].c - (sum[i].t * d);
        //printf("%lf ", parti[i]);
    }
   // printf("\n\n");

    while(!sw.empty()) {
        sw.pop_front();
    }
    double last = 0;
    bool found = false;
    int i = 1;
    while(i <= n && !found) {
        if(i >= a) {
            while(!sw.empty() && parti[i] < parti[sw.back()]) {
                sw.pop_back();
            }
            sw.push_back(i - a);
            if(sw.front() <= i - b - 1) {
                sw.pop_front();
            }
            /*
            for(auto &it : sw) {
                printf("%d ", it);
            }
            */
            if(parti[i] - parti[sw.front()] >= 0) {
                found = true;
            }
        }
        //printf("\n-------\n");
        i++;
    }

    return found;
}

int main ()
{


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

    fscanf(in, "%d%d%d", &n, &a, &b);

    sum[0].c = 0;
    sum[0].t = 0;
    for(int i = 1; i <= n; i++) {
        fscanf(in, "%d", &v[i].c);
        sum[i].c = sum[i - 1].c + v[i].c;
    }
    for(int i = 1; i <= n; i++) {
        fscanf(in, "%d", &v[i].t);
        sum[i].t = sum[i - 1].t + v[i].t;
    }

    double st = 0;
    double dr = 1;
    double mij;
    for(int i = 1; i <= 60; i++) {
        mij = (st + dr) / 2;
        if(merji(mij)) {
            st = mij;
        } else {
            dr = mij;
        }
    }

    fprintf(out, "%lf\n", st);

    fclose(in);
    fclose(out);

    return 0;
}