Pagini recente » Cod sursa (job #705948) | Cod sursa (job #2296196) | Cod sursa (job #2363586) | Cod sursa (job #464547) | Cod sursa (job #1497677)
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("balans.in");
ofstream g("balans.out");
int N,M,R,C;
double Matrix[305][305];
double Part[305][305];
const double eps = 0.001;
double Left,Right=100000,mid,sol,Max;
void Read()
{
f>>N>>M>>R>>C;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
f>>Matrix[i][j];
for(int i=N+1;i<=2*N;i++)
for(int j=1;j<=M;j++)
Matrix[i][j]=Matrix[i-N][j];
for(int i=1;i<=N;i++)
for(int j=M+1;j<=2*M;j++)
Matrix[i][j]=Matrix[i][j-M];
N*=2;
M*=2;
}
inline double sum(int x1,int y1,int x2,int y2)
{
return Part[x2][y2]-Part[x1-1][y2]-Part[x2][y1-1]+Part[x1-1][y1-1];
}
double maxSum(double X)
{
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
Part[i][j]=Part[i-1][j]+Part[i][j-1]-Part[i-1][j-1]+Matrix[i][j]-X;
Max=-2000000005;
for(int i=1;i<=N;i++)
for(int j=i+R-1;j<=N;j++)
{
double MMax,m=sum(i,1,j,C);
MMax=m;
for(int k=C+1;k<=M;k++)
{
m=max(m+sum(i,k,j,k),sum(i,k,j,k));
MMax=max(MMax,m);
}
Max=max(Max,MMax);
}
return Max;
}
void binSearch()
{
int count=30;
while(Left<=Right && count>=0)
{
mid=(Left+Right)/2;
if(maxSum(mid)>0)
{
Left=mid+0.001;
sol=mid;
continue;
}
if(maxSum(mid)<=0)
{
Right=mid-0.001;
continue;
}
}
g<<fixed<<setprecision(3)<<sol<<"\n";
}
int main()
{
Read();
binSearch();
return 0;
}