Mai intai trebuie sa te autentifici.
Cod sursa(job #554940)
Utilizator | Data | 15 martie 2011 10:41:08 | |
---|---|---|---|
Problema | Secventa 3 | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.99 kb |
#include <cstdio>
#define ll long long
#define N 30010
int n,lmin,lmax;
ll v1[N],v2[N];
ll v[N];
ll d[N];
inline void citire() {
scanf("%d%d%d",&n,&lmin,&lmax);
int x;
for(int i=1; i<=n; ++i) {
scanf("%d",&x);
v1[i] = (ll)x*100LL;
v1[i] += v1[i-1];
}
for(int i=1; i<=n; ++i) {
scanf("%d",&x);
v2[i] = (ll)x;
v2[i] += v2[i-1];
}
}
inline bool vezi(ll rez) {
int p=1,u=0;
for(int i=1; i<=n; ++i)
v[i] = v1[i]-v2[i]*rez;
for(int i=lmin+1; i<=n; ++i) {
if(p<=u && i-d[p]>lmax)
++p;
while(p<=u && v[d[u]]>=v[i-lmin])
--u;
d[++u] = i-lmin;
if(p<=u && v[d[p]]<=v[i])
return true;
}
return false;
}
inline void rezolva() {
int p=1,u=100000,m;
while(p+1<u) {
m = (p+u)>>1;
if(vezi(m))
p = m;
else
u = m-1;
}
if(vezi(p+1))
++p;
printf("%d.%.2d\n",p/100,p%100);
}
int main() {
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
citire();
rezolva();
return 0;
}