Pagini recente » Cod sursa (job #181986) | Cod sursa (job #550445) | Cod sursa (job #2808603) | Cod sursa (job #389162) | Cod sursa (job #999555)
Cod sursa(job #999555)
#include<fstream>
#include<cstdio>
#include<deque>
#include<cassert>
using namespace std;
int n,m,R,C,mat[310][310];
int M[310][310];
long long sum[310],sumC[310][310];
deque <int> D;
inline bool Posibil(int X)
{
int i,j,k;
long long best=-10000000000000000LL;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
M[i][j]=10000*mat[i][j]-X;
sumC[i][j]=sumC[i-1][j]+1LL*M[i][j];
}
}
for(i=1;i<=n;i++)
{
for(k=i+R-1;k<=n;k++)
{
if(k-i+1>n/2)
continue;
sum[0]=0;
for(j=1;j<=m;j++)
sum[j]=sum[j-1]+sumC[k][j]-sumC[i-1][j];
D.clear();
for(j=C;j<=m;j++)
{
while(D.size() && sum[D.back()]>=sum[j-C])
D.pop_back();
D.push_back(j-C);
while(D.front()<j-m/2)
D.pop_front();
best=max(best,sum[j]-sum[D.front()]);
}
}
}
if(best>=0)
return true;
return false;
}
inline double CautareBinara()
{
int st,dr,mij,rez=0;
st=0;
dr=1000000000;
while(st<=dr)
{
mij=(st+dr)/2;
if(Posibil(mij))
{
rez=mij;
st=mij+1;
}
else
dr=mij-1;
}
return (1.0*rez)/10000.0;
}
int main()
{
int i,j;
ifstream fin("balans.in");
fin>>n>>m>>R>>C;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
fin>>mat[i][j];
assert(0<=mat[i][j] && mat[i][j]<=100000);
mat[i+n][j]=mat[i][j+m]=mat[i+n][j+m]=mat[i][j];
}
}
n*=2;
m*=2;
fin.close();
freopen("balans.out","w",stdout);
printf("%.4lf\n",CautareBinara());
return 0;
}