Cod sursa(job #96286)

Utilizator megabyteBarsan Paul megabyte Data 31 octombrie 2007 21:26:33
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <cmath>
#define INF "secv3.in"
#define OUF "secv3.out"
#define NMAX 30002
#define EPS 1e-4
using namespace std;
long long n,l,u,c[NMAX],t[NMAX];

long long sumk(long long k)
{
    long long i,p,q,ok,dq[NMAX],p1,p2;
    long long v[NMAX],max;
    v[0]=0;
    for(i=1;i<=n;++i) v[i]=(c[i]-k*t[i])+v[i-1];//printf("%d ",v[i]);}
    //printf("\n");
    max=-1000000;ok=0;
    if(v[l]>max) max=v[l];
    if(max>0) ok=1;
    p=1;q=0;  i=l+1;
    while(i<=n)
    {
           dq[++q]=i-l;
           if(dq[p]<i-u) ++p;
           while(q>p&&v[i-l]<v[dq[q-1]])
           {
              --q;
              dq[q]=i-l;
           }
           if(v[i]-v[dq[p]]>max)
           {
                                  max=v[i]-v[dq[p]];
                                  if(max>0) ok=1;
              p1=i;p2=dq[p]+1;
           }
           ++i;
    }
    //printf("%d %d \n",p1,p2);
    return ok;
}
      
int main()
{
    long long i,max,st,dr,mij,c1,c2;
    FILE *in,*out;
    in=fopen(INF,"r");
    out=fopen(OUF,"w");
    fscanf(in,"%lld%lld%lld",&n,&l,&u);
    c[0]=t[0]=0;
    for(i=1;i<=n;++i) {fscanf(in,"%lld",c+i);c[i]*=100;}
    for(i=1;i<=n;++i) {fscanf(in,"%lld",t+i);t[i]*=1;}
    st=1;dr=100000;max=0;
    while(st<=dr)
    {
                 mij=(st+dr)/2;
                 if(sumk(mij))
                 {
                            max=mij;
                            st=mij+1;
                 }
                 else dr=mij-1;
    }
//    printf("%d\n",max);
    c1=(max/10)%10;c2=max%10;    
    fprintf(out,"%lld.%lld%lld\n",max/100,c1,c2);
//    printf("%d",max);
//    scanf("%d",&i);
    fclose(in);fclose(out);
    return 0;
}