Cod sursa(job #2217068)

Utilizator Alex62493Manghiuc Alexandru Alex62493 Data 28 iunie 2018 21:00:31
Problema Secventa 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>

using namespace std;

int l, u, n, i;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

class sir
{
public:
    int timp, nr;
};

sir v[30001];

float spate(int poz1, int poz2, float m, int a, int b)
{
    for (i=poz2; i>=poz1+l; i--)
    {
        a=a-v[i].nr;
        b=b-v[i].timp;
        if (1.00*a/b>m)
            m=1.00*a/b;
    }
    return m;
}

void backtracking()
{
    int a=0, b=0, poz1, poz2;
    float m;
    for (i=1; i<=u; i++)
    {
        a=a+v[i].nr;
        b=b+v[i].timp;
    }
    m=1.00*a/b;
    poz1=1;
    poz2=u;
    while(poz1!=n-l+1)
    {
        if (poz1==1)
        {
            m=spate(poz1, poz2, m, a, b);
            poz1++;
            a=a-v[1].nr;
            b=b-v[1].timp;
            if (1.00*a/b>m)
                m=1.00*a/b;
        }
        else if (poz2<n)
        {
            m=spate(poz1, poz2, m, a, b);
            poz2++;
            a=a+v[poz2].nr;
            b=b+v[poz2].timp;
            if (1.00*a/b>m)
                m=1.00*a/b;
            poz1++;
            a=a-v[poz1-1].nr;
            b=b-v[poz1-1].timp;
            if (1.00*a/b>m)
                m=1.00*a/b;
        }
        else
        {
            m=spate(poz1, poz2, m, a, b);
            poz1++;
            a=a-v[poz1-1].nr;
            b=b-v[poz1-1].timp;
            if (1.00*a/b>m)
                m=1.00*a/b;
        }
    }
    fout<<m;
}

int main()
{
    fin>>n>>l>>u;
    for (i=1; i<=n; i++)
    {
        fin>>v[i].nr;
    }
    for (i=1; i<=n; i++)
    {
        fin>>v[i].timp;
    }
    backtracking();
    return 0;
}