Pagini recente » Cod sursa (job #2799508) | Cod sursa (job #2969778) | Cod sursa (job #1587985) | Cod sursa (job #531789) | Cod sursa (job #332955)
Cod sursa(job #332955)
#include <stdio.h>
#include <assert.h>
#define maxn 200010
#define INF 30001000
int N, L, NR, i, P, U, aux1, paux1;
int A[maxn], Heap[maxn], Pos[maxn], B[maxn], SA[maxn], SB[maxn];
double maxim;
void push(int x){
int aux;
/*
(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])
(SA[i]-SA[Heap[x/2]-1]) / (SB[i]-SB[Heap[x/2]-1])
*/
while (x/2 && (double)(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])>(double)(SA[i]-SA[Heap[x/2]-1]) / (SB[i]-SB[Heap[x/2]-1])){
aux = Heap[x];
Heap[x] = Heap[x/2];
Heap[x/2] = aux;
Pos[Heap[x]] = x;
Pos[Heap[x/2]] = x/2;
x /= 2;
}
}
void pop(int x){
int aux, y = 0;
while (x != y) {
y = x;
/*
(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])
(SA[i]-SA[Heap[y*2+1]-1]) / (SB[i]-SB[Heap[y*2+1]-1])
*/
if (y*2<=L && (double)(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])<(double)(SA[i]-SA[Heap[y*2]-1]) / (SB[i]-SB[Heap[y*2]-1])) x = y*2;
if (y*2+1<=L && (double)(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])<(double)(SA[i]-SA[Heap[y*2+1]-1]) / (SB[i]-SB[Heap[y*2+1]-1])) x = y*2+1;
aux = Heap[x];
Heap[x] = Heap[y];
Heap[y] = aux;
Pos[Heap[x]] = x;
Pos[Heap[y]] = y;
}
}
int main()
{
FILE *f = fopen("secv3.in", "r");
FILE *g = fopen("secv3.out", "w");
fscanf(f, "%d %d %d", &N, &P, &U);
assert(1<=N && N<=200000);
for (i=1;i<=N;i++) {
fscanf(f, "%d", &A[i]);
SA[i] = SA[i-1] + A[i];
}
for (i=1;i<=N;i++) {
fscanf(f, "%d", &B[i]);
SB[i] = SB[i-1] + B[i];
}
for (i=P;i<=N;i++) {
//bag in heap pozitia i-p+1
L++;
Heap[L] = i-P+1;
Pos[i-P+1] = L;
push(L);
if (i>U) {
//scot din heap pozitia i-U+1
SA[i-U-1] = -INF;
push(Pos[i-U]);
Pos[Heap[1]] = 0;
Heap[1] = Heap[L--];
Pos[Heap[1]] = 1;
if (L>1) pop(1);
}
if ((double)(SA[i]-SA[Heap[1]-1]) / (SB[i]-SB[Heap[1]-1]) > maxim) {
maxim = (double)(SA[i]-SA[Heap[1]-1]) / (SB[i]-SB[Heap[1]-1]);
}
}
fprintf(g,"%lf",maxim);
fclose(f);
fclose(g);
return 0;
}