Pagini recente » Cod sursa (job #1793202) | Cod sursa (job #1063877) | Cod sursa (job #2296835) | Cod sursa (job #1872378) | Cod sursa (job #1611260)
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#define fact 10000
#define ll long long
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
deque <int> q;
int n,l,u,a[30005],b[30005];
ll s[30005];
int Ans(int r)
{ int i; ll sol,vmin;
for(i=1;i<=n;i++)
{s[i]=(ll) s[i-1]+a[i]-1LL*b[i]*r;
// cout<<s[i]<<"\n";
}
q.clear();
for(i=1;i<=n;i++)
{
if (i-l>=0)
{ while(!q.empty() && s[i-l]<=s[q.back()]) q.pop_back();
q.push_back(i-l);
}
while(!q.empty() && q.back()<=i-u-1) q.pop_back();
if (!q.empty())
{vmin=s[q.back()];
//cout<<i<<" "<<s[i]<<" "<<vmin<<"\n";
sol=s[i]-vmin;
if (sol>=0) return 1;
}
}
return 0;
}
void Search()
{ int st=0,dr=30005*fact,mid;
while(st<=dr)
{ mid=(st+dr)/2;
if (Ans(mid)) st=mid+1; else dr=mid-1;
cout<<mid<<" "<<Ans(mid)<<"\n";
}
mid=(st+dr)/2;
// if (!Ans(mid)) mid--;
g<<fixed<<setprecision(4)<<(double)mid/fact<<"\n";
}
int main()
{ int i,j,t; double sol=0,s1,s2;
f>>n>>l>>u;
srand(time(NULL));
i=rand()+rand()-rand();
for(i=1;i<=n;i++)
{
f>>a[i];
a[i]*=fact;
}
for(i=1;i<=n;i++)
{
f>>b[i];
}
/* for(i=1;i<=n;i++)
for(j=i+l-1;j<=i+u-1;j++)
{ s1=0; s2=0;
for(t=i;t<=j;t++)
{ s1+=a[t]/100; s2+=b[t]; }
if ((double) s1/s2>(double) sol) sol=(double) s1/s2;
} */
Search();
/* g<<fixed<<setprecision(2)<<sol<<"\n";
for(i=1;i<=n;i++)
g<<a[i]/100<<" ";
g<<"\n";
for(i=1;i<=n;i++)
g<<b[i]<<" ";
*/
return 0;
}