Pagini recente » Cod sursa (job #1951768) | Cod sursa (job #1473327) | Cod sursa (job #442287) | Cod sursa (job #2899646) | Cod sursa (job #386941)
Cod sursa(job #386941)
#include <fstream>
#include <deque>
using namespace std;
#define val first
#define poz second
const int MAX_N = 305;
const int INF = 0x3f3f3f3f;
ifstream fin ("balans.in");
ofstream fout ("balans.out");
int N, M, R, C, Max, A[MAX_N][MAX_N];
long long S[MAX_N][MAX_N], T[MAX_N];
void citire()
{
fin >> N >> M >> R >> C;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
{
fin >> A[i][j];
A[i][j] *= 1000;
Max = max(Max, A[i][j]);
}
for(int i = 1; i <= N; ++i)
for(int j = M+1; j <=2*M; ++j)
A[i][j] = A[i][j-M];
for(int i = N+1; i <= 2*N; ++i)
for(int j = 1; j <= 2*M; ++j)
A[i][j] = A[i-N][j];
}
bool works(int x)
{
for(int i = 1; i <= 2*N; ++i)
for(int j = 1; j <= 2*M; ++j)
S[i][j] = S[i-1][j] + A[i][j] - x;
int Sol = -INF;
for(int i = 1; i <= N; ++i)
for(int k = i+R-1; k <= i+N-1; ++k)
{
deque <pair<long long, int> > Q;
for(int j = 1; j <= 2*M; ++j)
T[j] = T[j-1] + S[k][j] - S[i-1][j];
for(int j = C; j <= 2*M; ++j)
{
while(!Q.empty() && Q.back().val > T[j-C]) Q.pop_back();
while(!Q.empty() && Q.front().poz < j - M) Q.pop_front();
Q.push_back(make_pair(T[j-C], j-C));
if(T[j] - Q.front().val > Sol)
Sol = T[j] - Q.front().val;
}
}
return (Sol >= 0);
}
void solve()
{
int lg = 1, i = 0;
for(; lg < Max; lg <<= 1);
for(; lg; lg >>= 1)
if(i + lg <= Max && works(i + lg))
i += lg;
fout << (i/1000) << "." << (i % 1000) << "\n";
}
int main()
{
citire();
solve();
}