Pagini recente » Cod sursa (job #2541395) | Cod sursa (job #2293586) | Cod sursa (job #582875) | Ciorna | Cod sursa (job #999575)
Cod sursa(job #999575)
#include<fstream>
#include<cstdio>
#include<deque>
#define LG 8000000
using namespace std;
int n,m,n2,m2,R,C,mat[310][310],ind;
long long sumC[310][310];
char buffer[LG];
inline void Citeste(int &x)
{
while(buffer[ind]<'0' || '9'<buffer[ind])
{
ind++;
if(ind==LG)
{
fread(buffer,1,LG,stdin);
ind=0;
}
}
x=0;
while('0'<=buffer[ind] && buffer[ind]<='9')
{
x=x*10+buffer[ind]-'0';
ind++;
if(ind==LG)
{
fread(buffer,1,LG,stdin);
ind=0;
}
}
}
inline bool Posibil(int X)
{
int i,j,k,sz=0;
long long best=-10000000000000000LL,sum[310];
deque <int> D;
for(i=1;i<=n;i++)
{
for(k=i+R-1;k-i+1<=n2 && k<=n;k++)
{
sum[0]=0;
for(j=1;j<=m;j++)
sum[j]=sum[j-1]+sumC[k][j]-sumC[i-1][j]-1LL*X*(k-i+1);
D.clear();
sz=0;
for(j=C;j<=m;j++)
{
while(sz && sum[D.back()]>=sum[j-C])
{
sz--;
D.pop_back();
}
D.push_back(j-C);
sz++;
while(D.front()<j-m2)
{
sz--;
D.pop_front();
}
best=max(best,sum[j]-sum[D.front()]);
}
if(best>=0)
return true;
}
}
return false;
}
inline int CautareBinara()
{
int st,dr,mij,rez=0;
st=0;
dr=100000000;
if(R==0 || C==0)
return 0;
while(st<=dr)
{
mij=(st+dr)/2;
if(Posibil(mij))
{
rez=mij;
st=mij+1;
}
else
dr=mij-1;
}
return rez;
}
int main()
{
int i,j;
freopen("balans.in","r",stdin);
fread(buffer,1,LG,stdin);
Citeste(n); Citeste(m); Citeste(R); Citeste(C);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
Citeste(mat[i][j]);
mat[i][j]*=1000;
mat[i+n][j]=mat[i][j+m]=mat[i+n][j+m]=mat[i][j];
}
}
n2=n;
m2=m;
n*=2;
m*=2;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
sumC[i][j]=sumC[i-1][j]+1LL*mat[i][j];
freopen("balans.out","w",stdout);
printf("%.3lf\n",(1.0*CautareBinara())/1000.0);
return 0;
}