Pagini recente » Cod sursa (job #1721257) | Cod sursa (job #1968254) | Cod sursa (job #2649993) | Cod sursa (job #989637) | Cod sursa (job #1780521)
#include <cstdio>
#define MAXN 150
#define INF 1000000000
long long mat[2*MAXN+1][2*MAXN+1];
long long v[2*MAXN+1];
long long sp[2*MAXN+1];
int dq[2*MAXN+1];
inline char cauta(long long med,int m,int c,int l1,int l2){
int i,b,e;
long long max;
b=0;
e=-1;
max=-INF;
for(i=1;i<2*m;i++){
sp[i]=sp[i-1]-med+mat[l2][i]-mat[l1][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,ans,rez,pas,max;
char flag;
fi=fopen("balans.in" ,"r");
fout=fopen("balans.out" ,"w");
fscanf(fi,"%d %d %d %d " ,&n,&m,&r,&c);
max=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
fscanf(fi,"%d " ,&mat[i][j]);
mat[i][j]*=1000;
if(mat[i][j]>max)
max=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;
rez=0;
pas=1;
while(pas<=max)
pas*=2;
pas/=2;
for(;pas;pas>>=1){
flag=0;
for(l1=0;l1<=2*n-r&&flag==0;l1++)
for(l2=l1+r;l2<=2*n&&flag==0;l2++)
if(l2-l1<=n){
if(cauta(1LL*(rez+pas)*(l2-l1),m,c,l1,l2)==1){
rez+=pas;
ans=rez;
flag=1;
}
}
}
fprintf(fout,"%d.%d" ,ans/1000,ans%1000);
fclose(fi);
fclose(fout);
return 0;
}