Pagini recente » Cod sursa (job #3329388) | Cod sursa (job #2959020) | Cod sursa (job #177525) | Cod sursa (job #3345629) | Cod sursa (job #3316647)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int N,L,U,spCost[30005],spTimp[30005],cost,timp;
void citireSiSp()
{
fin>>N>>L>>U;
for(int i=1;i<=N;i++)
{
fin>>cost;
spCost[i]=spCost[i-1]+cost;
}
for(int i=1;i<=N;i++)
{
fin>>timp;
spTimp[i]=spTimp[i-1]+timp;
}
}
bool f2(double x, int i, int j)
{
double a = spCost[i] - x * spTimp[i];
double b = spCost[j] - x * spTimp[j];
return a < b;
}
bool check(double x)
{
deque<int> dq;
for(int i=1;i<=N;i++)
{
if(i>U)
{
if (dq.empty()==0 && dq.front()<i-U)
{
dq.pop_front();
}
}
if(i>L)
{
while(dq.empty()==0 && f2(x,i-L,dq.back()))
{
dq.pop_back();
}
dq.push_back(i-L);
}
if(dq.empty()==0 && f2(x, i, dq.front())==0)
{
return 1;
}
}
return 0;
}
void cautareBinara()
{
double st=0, dr=1005,sol,x;
///log(1000) pana ajung cu st si dr la dist de 1, log(100) pana ajung la precision 2
/// ~20 op
for(int i=0;i<=100;i++)
{
x=(st+dr)/2;
bool ok=check(x);
if(ok==1)
{
/// x <= solutia cautata
st=x;
sol=x;
}
else
{
/// x > solutia cautata
dr=x;
}
}
fout<<fixed<<setprecision(3)<<sol;
}
int main()
{
citireSiSp();
cautareBinara();
return 0;
}