Pagini recente » Cod sursa (job #450367) | Cod sursa (job #2726679) | Cod sursa (job #2271224) | Cod sursa (job #2892172) | Cod sursa (job #1780496)
#include <cstdio>
#define MAXN 150
#define INF 1000000000
const double EPS=0.001;
int mat[2*MAXN+1][2*MAXN+1];
int v[2*MAXN+1];
double sp[2*MAXN+1];
int dq[2*MAXN+1];
inline char cauta(double med,int m,int c){
int i,b,e;
double max;
for(i=1;i<=2*m;i++)
sp[i]=sp[i-1]+v[i]-med;
b=0;
e=-1;
max=-INF;
for(i=1;i<=2*m;i++){
if(e>=b&&dq[b]<i-m)
b++;
if(i-c>=0){
while(e>=b&&sp[i-c]<=sp[dq[e]])
e--;
dq[++e]=i-c;
if(sp[i]-sp[dq[b]]>max)
max=sp[i]-sp[dq[b]];
}
}
if(max>=0)
return 1;
return 0;
}
int main(){
FILE*fi,*fout;
int i,j,n,m,r,c,l1,l2;
double ans,rez,pas;
fi=fopen("balans.in" ,"r");
fout=fopen("balans.out" ,"w");
fscanf(fi,"%d %d %d %d " ,&n,&m,&r,&c);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
fscanf(fi,"%d " ,&mat[i][j]);
mat[i+n][j]=mat[i][j];
mat[i][j+m]=mat[i][j];
mat[i+n][j+m]=mat[i][j];
}
for(i=1;i<=2*n;i++)
for(j=1;j<=2*m;j++)
mat[i][j]+=mat[i-1][j];
ans=0;
for(l1=0;l1<=2*n-r;l1++)
for(l2=l1+r;l2<=2*n;l2++)
if(l2-l1<=n){
for(j=1;j<=2*m;j++)
v[j]=mat[l2][j]-mat[l1][j];
rez=0;
pas=1;
for(i=1;i<=16;i++)
pas*=2;
for(;pas>=EPS;pas/=2)
if(cauta((rez+pas)*(l2-l1),m,c)==1)
rez+=pas;
if(ans<rez)
ans=rez;
}
fprintf(fout,"%.3lf" ,ans);
fclose(fi);
fclose(fout);
return 0;
}