Mai intai trebuie sa te autentifici.
Cod sursa(job #1254553)
Utilizator | Data | 2 noiembrie 2014 21:45:18 | |
---|---|---|---|
Problema | Secventa 3 | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.23 kb |
#include <fstream>
#include <iomanip>
#include<deque>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
const double mde = 0.001;
const int nmax = 30006, inf = 2000000000;
double m[nmax], v[nmax], sum[nmax], rasp;
int n, u, l;
bool verificare(double x)
{
for(int i = 1; i<=n; i++)
{
sum[i] = sum[i - 1] + m[i] - x * v[i];
}
deque <int> d;
for(int i = l; i<=n; i++)
{
while(!d.empty() && sum[i-l]<=sum[d.back()])
d.pop_back();
d.push_back(i - l);
if(d.front()==i - u - 1)
d.pop_back();
if(sum[i]>sum[d.front()])
{
return 1;
}
}
return 0;
}
void bs()
{
double lo = 0, hi = (double)inf, mid;
while(hi - lo>=0)
{
mid = (lo + hi)/2;
if(verificare(mid)==1)
{
rasp = mid;
lo = mid + mde;
}
else
{
hi = mid - mde;
}
}
}
int main(){
int player_unu=0;
in>>n>>l>>u;
for(int i = 1; i<=n; i++)
{
in>>m[i];
}
for(int i = 1; i<=n; i++)
{
in>>v[i];
}
bs();
out<<setprecision(2)<<fixed;
out<<rasp<<'\n';
return player_unu;
}