Pagini recente » Cod sursa (job #2939096) | Cod sursa (job #560090) | Cod sursa (job #2764503) | Cod sursa (job #872969) | Cod sursa (job #1497367)
#include <fstream>
#include <iomanip>
#include <deque>
#define lint long long int
using namespace std;
const int NMAX = 155;
int n, m, r, c;
int mat[2 * NMAX][2 * NMAX];
lint s_part[2 * NMAX][2 * NMAX];
deque <int> coada;
inline lint sum (int l1, int l2, int c, int x) {
return s_part[l2][c] - s_part[l1 - 1][c] - c * (l2 - l1 + 1ll) * x;
}
bool exists (int x) {
int j, k;
for (int i = 1; i <= 2 * n; ++ i) {
for (j = i + r - 1; j <= 2 * n && j <= i + n - 1; ++ j) {
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() && sum(i, j, coada.back(), x) >= sum(i, j, k - c, x))
coada.pop_back();
coada.push_back(k - c);
if (sum(i, j, k, x) - sum(i, j, coada.front(), x) >= 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 <= n; ++ i)
for (j = 1; j <= m; ++ j)
mat[i][j] *= 1000;
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];
s_part[i][j] = mat[i][j] + s_part[i][j - 1] + s_part[i - 1][j] - s_part[i - 1][j - 1];
}
/*int st = 1;
int dr = 100000000;
int ans = 0;
int mijl;
while (st <= dr) {
mijl = (st + dr) >> 1;
if (exists(mijl)) {
ans = mijl;
st = mijl + 1;
}
else
dr = mijl - 1;
}*/
int ans = 0;
for (int steps = 26; steps >= 0; -- steps)
if (exists(ans | (1 << steps)))
ans |= (1 << steps);
cout << fixed << setprecision(3) << ans / 1000 << '.' << setw(3) << setfill('0') << ans % 1000 << '\n';
cin.close();
cout.close();
return 0;
}