Pagini recente » Cod sursa (job #1900084) | Cod sursa (job #2959524) | Cod sursa (job #1188540) | Cod sursa (job #2130649) | Cod sursa (job #1497344)
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
const int NMAX = 155;
int n, m, r, c;
int mat[2 * NMAX][2 * NMAX];
double s_part[2 * NMAX];
deque <int> coada;
bool exists (double x) {
int j, k;
double sum;
for (int i = 1; i <= 2 * n; ++ i) {
for (k = 1; k <= 2 * m; ++ k)
s_part[k] = 0;
for (j = i; j <= 2 * n && j <= i + n - 1; ++ j) {
sum = 0;
for (k = 1; k <= 2 * m; ++ k) {
sum += (mat[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[k] - s_part[coada.front()] >= 0)
return true;
}
}
}
}
return false;
}
int main()
{
ifstream cin("balans.in");
ofstream cout("balans.out");
cin >> n >> m >> r >> c;
if (!r) r = 1;
if (!c) c = 1;
int j;
for (int i = 1; i <= n; ++ i)
for (j = 1; j <= m; ++ j)
cin >> mat[i][j];
for (int i = 1; i <= 2 * n; ++ i)
for (j = 1; j <= 2 * m; ++ j)
mat[i][j] = mat[(i - 1) % n + 1][(j - 1) % m + 1];
double st = 0;
double dr = 100000;
double mijl;
for (int steps = 0; steps < 35; ++ steps) {
mijl = (st + dr) * 0.5;
if (exists(mijl))
st = mijl;
else
dr = mijl;
}
cout << fixed << setprecision(3) << st << '\n';
cin.close();
cout.close();
return 0;
}