Pagini recente » Cod sursa (job #141525) | Cod sursa (job #1857697) | Cod sursa (job #402862) | Cod sursa (job #62744) | Cod sursa (job #992418)
Cod sursa(job #992418)
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;
const string file = "secv3";
const string infile = file + ".in";
const string outfile = file + ".out";
const int INF = 0x3f3f3f3f;
int N, L, U;
vector<int> cs;
vector<int> ts;
int MaxC;
int MinT;
double MaxR;
void pushb(deque<int>& d, int& cC, int& cT, int i)
{
d.push_back(i);
cC += cs[i];
cT += ts[i];
}
void popf(deque<int>& d, int& cC, int& cT)
{
int idx = d.front();
d.pop_front();
cC -= cs[idx];
cT -= ts[idx];
}
void solve()
{
deque<int> removables;
deque<int> musts;
int cC = 0;
int cT = 0;
int rC = 0;
int rT = 0;
for(int i = 0; i < L; i++)
{
pushb(musts, cC, cT, i);
}
MaxC = cC;
MinT = cT;
MaxR = (double)1 * MaxC / MinT;
for(int i = L; i < N; i++)
{
pushb(musts, cC, cT, i);
pushb(removables, rC, rT, musts.front());
popf(musts, cC, cT);
if((int)removables.size() > U - L)
{
popf(removables, rC, rT);
}
while(removables.size() > 0 )
{
int xC = cs[removables.front()];
int xT = ts[removables.front()];
if((double)1 * xC / xT > (double)1 * (cC + rC - xC)/(cT + rT - xT))
{
break;
}
popf(removables, rC, rT);
}
if(removables.size() > 0)
{
if((double)1 * rC / rT <= (double) 1 * cC / cT)
{
removables.clear();
rC = 0;
rT = 0;
}
}
int newMaxC = cC + rC;
int newMinT = cT + rT;
double newMaxR = (double)1 * newMaxC / newMinT;
if(newMaxR > MaxR)
{
MaxR = newMaxR;
MaxC = newMaxC;
MinT = newMinT;
}
}
}
int main()
{
fstream fin(infile.c_str(), ios::in);
fin >> N >> L >> U;
cs.resize(N);
ts.resize(N);
for(int i = 0; i < N; i++)
{
fin >> cs[i];
}
for(int i = 0; i < N; i++)
{
fin >> ts[i];
}
fin.close();
solve();
fstream fout(outfile.c_str(), ios::out);
fout << fixed << setprecision(3) << MaxR << "\n";
fout.close();
}