Nu aveti permisiuni pentru a descarca fisierul grader_test4.in
Cod sursa(job #2668863)
| Utilizator | Data | 5 noiembrie 2020 16:55:46 | |
|---|---|---|---|
| Problema | Secventa 3 | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 1.6 kb |
#include<iostream>
#include<fstream>
#include<deque>
#include<iomanip>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
const double DIF = 0.0001;
int n, l, u;
double st = 0.0, dr = 1000.0;
int c[30100], t[30100];
double v[30100];
bool check(double value)
{
for(int i = 1; i <= n; i++)
v[i] = c[i] - t[i] * value;
/*if(value == 500.0)
{
for(int i = 1; i <= n; i++)
cout << v[i] << ' ';
cout << '\n';
}*/
deque<pair<double, int>> dq;
for(int i = l; i <= n; i++)
{
while(!dq.empty() && v[i - l] < dq.back().first)
dq.pop_back();
dq.emplace_back(v[i - l], i - l);
if(dq.front().second < i - u)
dq.pop_front();
if(i >= l && v[i] - dq.front().first >= 0.0)
{
//cout << i << ' ' << dq.front().second << '\n';
return 1;
}
//if(value == 500.0)
//cout << i << ' ' << dq.front().second << '\n';
}
return 0;
}
int main()
{
in >> n >> l >> u;
for(int i = 1; i <= n; i++)
{
int x;
in >> x;
c[i] = x + c[i - 1];
}
for(int i = 1; i <= n; i++)
{
int x;
in >> x;
t[i] = x + t[i - 1];
}
while(dr - st > DIF)
{
double mid = (st + dr) / 2;
//cout << mid << ' ' << check(mid) << '\n';
if(check(mid))
st = mid;
else
dr = mid;
}
out << fixed << setprecision(2) << st << '\n';
return 0;
}
