Pagini recente » Istoria paginii runda/hk | Clasament test_123 | Cod sursa (job #1603876) | Istoria paginii runda/un_ultim_efort | Cod sursa (job #493840)
Cod sursa(job #493840)
#include<stdio.h>
int a[ 310 ][ 310 ],n,m,r,c,i,j,k,l,p,u,dp[ 310 ];
double d[ 310 ],bmax;
void citire(){
freopen("balans.in","r",stdin);
scanf("%d %d %d %d",&n,&m,&r,&c);
for(i = 1 ; i <= n ; i++)
for(j = 1;j<=m;j++)
scanf("%d",&a[i][j]);
}
double medie(int i1,int j1,int i2,int j2){
int s,n;
s = a[i2][j2] - a[i1-1][j2] - a[i2][j1-1]+a[i1-1][j1-1];
n = (i2- i1+1)*(j2-j2+1);
return (double)(s)/(double)(n);
}
int bs(double val,int u){
int p,m,sol = 1;
p = 1;
while(p<=u)
{m = (p+u)>>1;
if(d[m] < val)
{sol = m;
p = m+1;
}
else
u = m-1;
}
return dp[sol];
}
void check(int i,int ii){
int p = 0;
double MC,poz;
for(int j = c ; j <= m ; j++)
{MC = medie(i,1,ii,j);
poz = bs(MC,p);
while(MC < d[p])
p--;
p++;
d[p] = MC;
dp[p] = j;
MC = medie(i,poz+1,ii,j);
if(MC >= bmax)
bmax = MC;
}
}
void solve(){
for(i = 1; i <= n ; i++)
for(j = 1 ; j <= m ; j++)
a[i+n][j] = a[i][j+m] = a[i+n][j+m] = a[i][j];
n = n<<1;
m = m<<1;
for(i=1;i<=n;i++)
for(j = 1 ; j <= m ; j++)
a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
int ii;
for(i = 1; i <= n ; i++)
for(ii = i+r-1 ; ii <= n ; ii++)
check(i,ii);
}
void afisare(){
freopen("balans.out","w",stdout);
printf("%0.3f",bmax);
}
int main(){
citire();
solve();
afisare();
return 0;
}