Cod sursa(job #409504)

Utilizator dgoldenAlex Popescu dgolden Data 3 martie 2010 18:21:32
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

#define FIN "secv3.in"
#define FOUT "secv3.out"
#define MAX_N 30005
#define INF 0x3f3f3f3f

double C[MAX_N];
double T[MAX_N];
int N, L, U;

double v[MAX_N];
int d[MAX_N]; // deque

    inline double max (double a, double b)
    {
           return (a > b) ? a : b;
    }

    int compute (double X)
    {
         memset(v, 0, sizeof (v));
         memset(d, 0, sizeof (d));
         double localBEST = -INF;
        
         for (int i = 1; i <= N; ++i)
             v[i] = C[i] - X * T[i] + v[i - 1];
             
         int li, lf;
         for (int i = 1, li = lf = 0; i <= N; ++i)
         {
             if (i - d[li] > U) ++li;
             if (i - d[li] >= L && li <= lf)
                localBEST = max(localBEST, v[i] - v[d[li]]);
             
             d[++lf] = i;
             while (lf > li && v[d[lf]] < v[d[lf - 1]]) d[--lf] = d[lf + 1];
         }
         
         //printf("%.10lf\n", localBEST);
         if (localBEST < 0) 
               return 0;
            else
               return 1;
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d %d", &N, &L, &U);
        for (int i = 1; i <= N; ++i) scanf ("%lf", C + i);
        for (int i = 1; i <= N; ++i) scanf ("%lf", T + i);
        
        double li = 0, lf = 1010, m;
        
        while (abs(li - lf) > 0.001)
              if (compute(m = (li + lf) / 2)) li = m + 0.001;
                         else lf = m - 0.001;
        
        printf ("%lf\n", m);
        
        return 0;
    }