Pagini recente » Cod sursa (job #1428490) | Cod sursa (job #2359303) | Istoria paginii runda/saaasssssss/clasament | Cod sursa (job #3205446) | Cod sursa (job #1720578)
#include <iostream>
#include<fstream>
#include<iomanip>
using namespace std;
const int en=155;
long long minim[2*en],deq[en],d[en],a[en][en],s[2*en][2*en],el;
int i,j,n,m,k,newi,newj,N,M,p,ul,em,u,pr,r,c,i1;
void build(int x)
{
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
{
newi=i,newj=j;
if(newi>n) newi-=n;
if(newj>m) newj-=m;
s[i][j]=s[i-1][j]+a[newi][newj]-x;
}
}
bool check(int x)
{
build(x);
for(i=r;i<=N;i++)
for(i1=max(0,i-n);i1<=i-r;i1++)
{
p=1;u=1;
d[u]=0;deq[u]=0;el=0;
for(j=1;j<=M;j++)
{
el+=s[i][j]-s[i1][j];
if(i-d[p]>=k) p++;
while(el<=deq[u]&&p<=u)
u--;
u++;
deq[u]=el;
d[u]=j;
minim[j]=deq[u];
if(j>=r) if(el-minim[j-c]>=0) return true;
}
}
return false;
}
int main()
{
ifstream f("balans.in");
ofstream g("balans.out");
f>>n>>m>>r>>c;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{f>>a[i][j];a[i][j]*=10000;}
pr=0;ul=1000000000;
N=2*n;M=2*m;
k=m-c;
while(ul-pr>1)
{
em=(pr+ul)/2;
if(check(em)) pr=em;
else ul=em;
}
double rasp=ul;
rasp/=10000;
g<<fixed<<setprecision(3)<<rasp;
return 0;
}