Pagini recente » Cod sursa (job #748519) | Cod sursa (job #2124580) | Cod sursa (job #369589) | Cod sursa (job #1323046) | Cod sursa (job #1590598)
#include <bits/stdc++.h>
#define maxN 302
using namespace std;
int n, m, c, r, a[maxN][maxN], i, j, k;
int sol, sum[maxN], aux;
int ii, jj;
int st, dr;
deque<int> q;
bool verif(int x)
{
int i, j, k;
for(i = 1; i <= n; i++)
{
memset(sum, 0, sizeof(sum));
//sume partiale
for(j = i; j < min(2*n, i+r-1); j++)
{
aux=0;
for(k = 1; k <= 2 * m; k++)
aux += a[j][k] - x, sum[k] += aux;
}
for(j = i+r-1; j <= min(2*n, i+n-1); j++)
{
aux=0;
for(k = 1; k <= 2*m; k++)
aux += a[j][k]-x, sum[k] += aux;
//min_deque
q.clear();
for(k = c; k <= 2*m; k++)
{
while(!q.empty() && sum[k-c] <= sum[q.front()])
q.pop_front();
while(!q.empty() && k-q.back() > m)
q.pop_back();
q.push_front(k-c);
if(sum[k] >= sum[q.back()]) return true;
}
}
}
return false;
}
void cb(int st, int dr)
{
int mij;
while(st <= dr)
{
mij = (st+dr)>>1;
if(verif(mij)) sol=mij, st = mij+1;
else dr = mij-1;
}
}
int main()
{
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
scanf("%d %d %d %d", &n, &m, &r, &c);
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
scanf("%d", &a[i][j]), a[i][j] *= 1000;
//circularitate
for(i = 1; i <= 2*n; i++)
for(j = 1; j <= 2*m; j++)
if(!(i <= n && j <= m))
{
ii = (i-1)%n+1;
jj = (j-1)%m+1;
a[i][j] = a[ii][jj];
}
//caut binar solutia
st=0, dr=(1<<27);
cb(st, dr);
printf("%d.%d", sol/1000, sol%1000);
return 0;
}