Pagini recente » Cod sursa (job #2202639) | Cod sursa (job #2027704) | Cod sursa (job #2461249) | Cod sursa (job #2603277) | Cod sursa (job #1497902)
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("balans.in");
ofstream g("balans.out");
int N,M,R,C;
long long Matrix[305][305],V[5];
long long Part[305][305];
const double eps = 0.001;
long long Left,Right=1000000000,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;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
Matrix[i][j]*=1000;
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];
}
inline long long sum(int x1,int y1,int x2,int y2,long long X)
{
return Part[x2][y2]-Part[x1-1][y2]-Part[x2][y1-1]+Part[x1-1][y1-1]-X*(x2-x1+1)*(y2-y1+1);
}
long long maxSum(long long X)
{
Max=-10000000000000000;
for(int i=1;i<=N;i++)
for(int j=i+R-1;j<=N;j++)
{
long long MMax,m=sum(i,1,j,C,X);
MMax=m;
for(int k=C+1;k<=M;k++)
{
m=max(m+sum(i,k,j,k,X),sum(i,k-C+1,j,k,X));
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+1;
sol=mid;
continue;
}
Right=mid-1;
}
g<<sol/1000<<".";
int aux=sol%1000;
while(aux!=0)
{
V[++V[0]]=aux%10;
aux/=10;
}
while(V[0]<3)
++V[0];
for(int i=V[0];i>=1;i--)
g<<V[i];
g<<"\n";
}
int main()
{
Read();
binSearch();
return 0;
}