Cod sursa(job #95329)

Utilizator anamaria1Ozorchevici Ana Maria anamaria1 Data 28 octombrie 2007 11:38:12
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<fstream.h>
#include<iomanip.h>
#define dim 30000
int cost[dim+1],timp[dim+1];
struct secv
 {unsigned long c,t;
 };
secv v[dim][2];
int main()
{ifstream f("secv3.in");
ofstream g("secv3.out");
int n,u,l,i,j,nr,nr2,n2,ok;
unsigned long maxt,maxc;
f>>n>>l>>u;
for(i=1;i<=n;i++) f>>cost[i];
for(i=1;i<=n;i++) f>>timp[i];
f.close();
v[1][0].c=v[1][0].t=0;
for(i=1;i<=l;i++) {v[1][0].c+=cost[i];v[1][0].t+=timp[i];}
maxc=v[1][0].c;maxt=v[1][0].t;
nr=1;
for(i=l+1;(i<=u)&&(i<=n);i++)
 {nr2=nr+1;
  v[nr2][0].c=v[nr][0].c+cost[i];v[nr2][0].t=v[nr][0].t+timp[i];
  if((maxc*v[nr2][0].t)<(maxt*v[nr2][0].c))
   {maxc=v[nr2][0].c;maxt=v[nr2][0].t;}
  nr=nr2;
 }
n2=n-l+1;ok=1;
for(i=2;i<=n2;i++)
 if(ok)
  {v[1][1].c=v[1][0].c-cost[i-1]+cost[i+l-1];
   v[1][1].t=v[1][0].t-timp[i-1]+timp[i+l-1];
   if((maxc*v[1][1].t)<(maxt*v[1][1].c))
    {maxc=v[1][1].c;maxt=v[1][1].t;}
   nr=1;
   for(j=l+1;(j<=u)&&((i+j-1)<=n);j++)
    {nr2=nr+1;
     v[nr2][1].c=v[nr][1].c+cost[i+j-1];v[nr2][1].t=v[nr][1].t+timp[i+j-1];
     if((maxc*v[nr2][1].t)<(maxt*v[nr2][1].c))
      {maxc=v[nr2][1].c;maxt=v[nr2][1].t;}
     nr=nr2;
    }
   ok=0;
  }
  else
   {v[1][0].c=v[1][1].c-cost[i-1]+cost[i+l-1];
    v[1][0].t=v[1][1].t-timp[i-1]+timp[i+l-1];
    if((maxc*v[1][0].t)<(maxt*v[1][0].c))
     {maxc=v[1][0].c;maxt=v[1][0].t;}
    nr=1;
    for(j=l+1;(j<=u)&&((i+j-1)<=n);j++)
     {nr2=nr+1;
      v[nr2][0].c=v[nr][0].c+cost[i+j-1];v[nr2][0].t=v[nr][0].t+timp[i+j-1];
      if((maxc*v[nr2][0].t)<(maxt*v[nr2][0].c))
       {maxc=v[nr2][0].c;maxt=v[nr2][0].t;}
      nr=nr2;
     }
    ok=1;
   }
g<<setprecision(2)<<((float)maxc/maxt)<<'\n';
g.close();
return 0;
}