Pagini recente » Cod sursa (job #1845787) | Cod sursa (job #2065584) | Cod sursa (job #1507693) | Cod sursa (job #1695495) | Cod sursa (job #1665487)
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
const int MAX = 30000;
int a[1 + MAX];
int b[1 + MAX];
int v[1 + MAX];
int n, l, u;
int ssm()
{
deque<int> dq;
int suma = 0;
int best = - MAX * 1001;
for(int i = 1; i <= l; i++)
{
suma = v[i];
/// insert in dq
while(!dq.empty() && v[dq.back()] > v[i - 1])
dq.pop_back();
dq.push_back(i - 1);
}
if(suma - v[dq.front()] > 0)
return 1;
for(int i = l + 1; i <= n; i++)
{
suma = v[i];
/// push in dq
while(!dq.empty() && v[dq.back()] >= v[i - 1])
dq.pop_back();
dq.push_back(i - 1);
/// pop in dq
if(!dq.empty() && dq.front() < i - u )
dq.pop_front();
if(!dq.empty() && suma - v[dq.front()] > 0)
return 1;
}
return 0;
}
bool verif(int x)
{
memset(v, 0, sizeof(v));
for(int i = 1; i <= n; i++)
v[i] = a[i] * 100 - b[i] * x + v[i - 1];
if(ssm() > 0)
return true;
return false;
}
int cb()
{
int i = 0, pas = 1 << 20;
while(pas)
{
if(verif(i + pas) == 1)
i += pas;
pas >>= 1;
}
return i;
}
int main()
{
FILE *fin, *fout;
fin = fopen("secv3.in", "r");
fout = fopen("secv3.out", "w");
fscanf(fin, "%d%d%d", &n, &l, &u);
for(int i = 1; i <= n; i++)
fscanf(fin, "%d", &a[i]);
for(int i = 1; i <= n; i++)
fscanf(fin, "%d", &b[i]);
fprintf(fout, "%.2f", (double) cb() / 100);
return 0;
}