Pagini recente » Cod sursa (job #875175) | Cod sursa (job #13680) | Cod sursa (job #3121371) | Cod sursa (job #1246319) | Cod sursa (job #1499025)
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("balans.in");
ofstream g("balans.out");
int N,M,R,C;
int Matrix[305][305],V[5];
long long Part[305][305];
long long Array[305];
int Deque[305];
const double eps = 0.001;
int Left,Right=1000000000,mid,sol,Max;
void Read()
{
f>>N>>M>>R>>C;
R=max(R,1);
C=max(C,1);
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]+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);
}
int Sum(int x,int y,long long X)
{
int Begin=1,End=0,point=1;
long long Max=-10000000000000000;
for(int i=1;i<=M;i++)
Array[i]=Array[i-1]+Part[y][i]-Part[x-1][i]-X*(y-x+1);
if(Array[C]>=0)
return 1;
for(int i=C+1;i<=M;i++)
{
while(Begin<=End && Array[i-C]<=Array[Deque[End]])
--End;
Deque[++End]=i-C;
if(Deque[Begin]==i-M/2-1)
++Begin;
if(Array[i]>=Array[Deque[Begin]])
return 1;
}
return -1;
}
int maxSum(long long X)
{
for(int i=1;i<=N/2;i++)
for(int j=i+R-1;j<=N && j-i+1<=N/2;j++)
{
if(Sum(i,j,X)>=0)
return 1;
}
return -1;
}
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;
}