Cod sursa(job #1236293)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 1 octombrie 2014 19:26:39
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#define Nmax 30005

using namespace std;
int N,A,B;
int V[Nmax],Cost[Nmax],Vpart[Nmax],Cpart[Nmax];
double DP[Nmax];
struct ele{
    ele(){
     a = b = 0;
    }
    ele(int a,int b){
        this->a = a;
        this->b = b;
    }
    int a,b;
}p[Nmax];


void read()
{
    scanf("%d%d%d",&N,&A,&B);
    for(int i = 1; i <= N; ++i)
    {
        scanf("%d",&V[i]);
        Vpart[i] = Vpart[i-1] + V[i];
    }
    for(int i = 1; i <= N; ++i)
    {
        scanf("%d",&Cost[i]);
        Cpart[i] = Cpart[i-1] + Cost[i];
    }
}

void solve()
{

    DP[A] = (1.0*Vpart[A]) / Cpart[A];
    p[A] = ele(1,A);
    double best = DP[A];
    int a = 1,b = A;
    for(int i = A + 1; i <= N; ++i)
    {
        if(b - a + 1 < B)
        {
            if( (DP[i-1] *(Cpart[p[i-1].b] - Cpart[p[i-1].a-1]) + V[i]) / (Cpart[i] - Cpart[p[i-1].a-1] ) > DP[i] )
            {
                DP[i] = (DP[i-1] *(Cpart[p[i-1].b] - Cpart[p[i-1].a-1]) + V[i]) / (Cpart[i] - Cpart[p[i-1].a-1] );
                p[i] = ele(p[i-1].a,p[i-1].b+1);
            }
        }
        else
            if( (DP[i-1] * (Cpart[p[i-1].b] - Cpart[p[i-1].a-1] + V[i] - V[p[i-1].a])) / (Cpart[i] - Cpart[p[i-1].a]) > DP[i] )
            {
                DP[i] = (DP[i-1] * (Cpart[p[i-1].b] - Cpart[p[i-1].a-1] + V[i] - V[p[i-1].a])) / (Cpart[i] - Cpart[p[i-1].a]);
                p[i] = ele(p[i-1].a+1,p[i-1].b+1);
            }
        if((1.0*(Vpart[i] - Vpart[i-A])) / (Cpart[i] - Cpart[i-A]) > DP[i])
        {
            DP[i] = (1.0*(Vpart[i] - Vpart[i-A])) / (Cpart[i] - Cpart[i-A]);
            p[i] = ele(i-A+1,i);
        }
        if(DP[i] > best)
            best = DP[i];
    }
    printf("%.2lf\n",best);
}

int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);

    read();
    solve();

    return 0;
}