Pagini recente » Cod sursa (job #1274691) | Cod sursa (job #2838768) | Cod sursa (job #870893) | Cod sursa (job #3128022) | Cod sursa (job #2333377)
#include <bits/stdc++.h>
using namespace std;
ifstream f("balans.in");
ofstream g("balans.out");
int i,j,k,n,m,r,c;
long long lo,hi,s_part[310],a[310][310];
deque<int> coada;
bool hmm(int x)
{
for(i=1;i<=2*n;i++)
{
for(k=1;k<=2*m;k++)
s_part[k]=0;
for(j=i;j<=2*m&&j<=i+n-1;j++)
{
long long sum=0;
for(k=1;k<=2*m;k++)
{
sum+=a[j][k]-x;
s_part[k]+=sum;
}
if(j<i+r-1)
continue;
coada.clear();
for(k=1;k<=2*m;k++)
{
while(!coada.empty()&&coada.front()<k-n)
coada.pop_front();
if(k>=c)
{
while(!coada.empty()&&s_part[coada.back()]>=s_part[k-c])
coada.pop_back();
coada.push_back(k-c);
if(s_part[coada.back()]<=s_part[k])
return true;
}
}
}
}
return false;
}
int main()
{
f>>n>>m>>r>>c;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
f>>a[i][j];
a[i][j]*=1000;
a[i][j+m]=a[i][j];
}
for(i=n+1;i<=2*n;i++)
for(j=1;j<=2*m;j++)
a[i][j]=a[i-n][j];
lo=0,hi=1e9;
while(lo<hi)
{
long long mi=(lo+hi)/2;
if(hmm(mi))
lo=mi+1;
else
hi=mi;
}
g<<fixed<<setprecision(3)<<(long double)(lo-1)/1000.0;
return 0;
}