Pagini recente » Cod sursa (job #2837547) | Cod sursa (job #1428744) | algoritmiada-2019/runda-preoji/clasament | Cod sursa (job #1956464) | Cod sursa (job #2154476)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in("balans.in");
ofstream out("balans.out");
typedef long long ll;
const int NMAX = 150;
const int NORM = 1e3;
int n, m, r, c;
ll res;
ll sum[1 + 2 * NMAX];
ll a[1 + 2 * NMAX][1 + 2 * NMAX];
ll sp[1 + 2 * NMAX][1 + 2 * NMAX];
ll maxx;
deque < int > dq;
bool ok(int x) {
fill(sum, sum + 2 * NMAX + 1, 0);
ll mx;
for(int l1 = 1; l1 <= n; l1++) {
for(int l2 = l1 + r - 1; l2 <= l1 + n - 1; l2++) {
for(int i = 1; i <= 2 * m; i++)
sum[i] = sum[i - 1] + sp[l2][i] - sp[l1 - 1][i] - (l2 - l1 + 1) * x;
dq.clear();
mx = sum[c];
dq.push_back(1);
for(int i = c + 1; i <= 2 * m; i++) {
while(!dq.empty() && dq.back() + m - 1 < i)
dq.pop_back();
while(!dq.empty() && sum[i] - sum[dq.front() - 1] <= sum[i] - sum[i - c])
dq.pop_front();
dq.push_front(i - c + 1);
mx = max(mx, sum[i] - sum[dq.back() - 1]);
if(m < dq.back())
break;
}
if(0 <= mx)
return true;
}
}
return false;
}
int main()
{
in >> n >> m >> r >> c;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
in >> a[i][j];
a[i][j] *= NORM;
maxx = max(maxx, a[i][j]);
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
for(int i = 1; i <= 2 * n; i++)
for(int j = 1; j <= 2 * m; j++)
sp[i][j] = sp[i - 1][j] + a[i][j];
int from = 0, to = maxx;
while(from <= to) {
ll mid = from + (to - from) / 2;
if(ok(mid) == true) {
res = mid;
from = mid + 1;
} else
to = mid - 1;
}
out << res / NORM << '.' << res % NORM << '\n';
in.close();
out.close();
return 0;
}