Pagini recente » Cod sursa (job #1696574) | Cod sursa (job #862514) | Cod sursa (job #1260074) | Cod sursa (job #1113261) | Cod sursa (job #1665529)
#include <stdio.h>
#include <queue>
using namespace std;
const int MAX = 30000;
int a[1 + MAX];
int b[1 + MAX];
long long v[1 + MAX];
int n, l, u;
int ssm()
{
deque<int> dq;
long long suma = 0;
for(int i = 1; i <= n; i++)
{
suma = v[i];
/// pop in dq
if(!dq.empty() && dq.front() < i - u )
dq.pop_front();
/// push in dq
if(i - l >= 0)
{
while(!dq.empty() && v[dq.back()] >= v[i - l])
dq.pop_back();
dq.push_back(i - l);
}
if(!dq.empty() && suma - v[dq.front()] >= 0)
return 1;
}
return 0;
}
bool verif(int x)
{
for(int i = 1; i <= n; i++)
v[i] = a[i] * 100 - b[i] * x + v[i - 1];
if(ssm() == 1)
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\n", (double) cb() / 100);
return 0;
}