Pagini recente » Cod sursa (job #1296127) | Cod sursa (job #3291914) | Cod sursa (job #3205508) | Cod sursa (job #387597) | Cod sursa (job #2350871)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150;
int n, m, r, c;
int mat[MAXN + 5][MAXN + 5];
long long v[2 * MAXN + 5], sp[2 * MAXN + 5];
int mod(int a)
{
if(a!=n)
a=a%n;
return a;
}
bool verif(int val)
{
for(int i=1; i+r-1<=2*n; i++)
{
for(int j=1; j<=2*m; j++)
v[j]=0;
for(int j=i; j<i+r-1; j++)
for(int k=1; k<=m; k++)
v[k]=v[k+m]=v[k]+mat[mod(j)][k]-val;
for(int j=i+r-1; j<=min(2*n,i+n-1); ++j)
{
for(int k=1; k<=m; k++)
v[k]=v[k+m]=v[k]+mat[mod(j)][k]-val;
for (int k=1;k<c;k++)
sp[k]=sp[k-1]+v[k];
deque<int>dq;
for(int k=c;k<2*m;k++)
{
sp[k]=sp[k-1]+v[k];
while(!dq.empty()&&sp[dq.back()]>=sp[k-c])
dq.pop_back();
dq.push_back(k-c);
if (sp[k]-sp[dq.front()]>= 0)
return 1;
if (dq.front()==k-m)
dq.pop_front();
}
}
}
return 0;
}
int main()
{
ifstream cin("balans.in");
ofstream cout("balans.out");
cin>>n>>m>>r>>c;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
{
cin>>mat[i][j];
mat[i][j]=mat[i][j]*1000;
}
int st=0,dr=100000005,last=0;
while(st<=dr)
{
int mij=(st+dr)/2;
if(verif(mij))
last=mij,st=mij+1;
else
dr=mij-1;
}
cout<<fixed<<setprecision(3)<<(double)last/1000;
return 0;
}