Nu exista pagina, dar poti sa o creezi ...
Cod sursa(job #2040746)
Utilizator | Data | 16 octombrie 2017 15:06:33 | |
---|---|---|---|
Problema | Secventa 3 | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.42 kb |
#include <iostream>
#include <cstdio>
#include <deque>
#define NMAX 30005
#define INF 0x3f3f3f
using namespace std;
int n, limMin, limMax, vElem[NMAX], vTimp[NMAX];
double vRez[NMAX];
deque <int> q;
void read()
{
scanf("%d%d%d", &n, &limMin, &limMax);
int nr;
///sume partiale
for(int i=1; i<=n; ++i)
{
scanf("%d", &nr);
vElem[i] = vElem[i-1] + nr;
}
for(int i=1; i<=n; ++i)
{
scanf("%d", &nr);
vTimp[i] = vTimp[i-1] + nr;
}
}
void resetDeque()
{
while(!q.empty())
q.pop_back();
}
int verifParte(double mijloc)
{
for(int i=1; i<=n; ++i)
vRez[i] = vElem[i] - (double)vTimp[i] * mijloc;
resetDeque();
for(int i=1; i<=n; ++i)
{
while(!q.empty() && vRez[i] <= vRez[q.back()])
q.pop_back();
q.push_back(i);
if(i - q.front() > limMax - limMin)
q.pop_front();
if(vRez[i+limMin] - vRez[q.front()] > 0 && i+limMin <= n)
return 1;
}
return 0;
}
int main()
{
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
read();
double st = 0, dr = INF;
///cautare binara
while(dr - st >= 0.001)
{
double mij = (dr + st)/2;
if(verifParte(mij))
st = mij;
else
dr = mij;
}
printf("%.2lf", st);
return 0;
}