Cod sursa(job #1247754)

Utilizator lupuflaviu9lupuflaviu lupuflaviu9 Data 23 octombrie 2014 17:18:05
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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;
}