Pagini recente » Cod sursa (job #2938815) | Cod sursa (job #2526597) | Cod sursa (job #2127080) | Cod sursa (job #2739673) | Cod sursa (job #2917282)
/// Preset de infoarena
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
const int maxN = 305;
const double eps = 1e-6;
int n, m, r, c;
int mat[maxN][maxN];
double aux[maxN][maxN], v[maxN];
deque <int> dq;
bool check(double val)
{
for(int i = 1; i <= 2*n; i++)
for(int j = 1; j <= 2*m; j++)
aux[i][j] = aux[i - 1][j] + mat[i][j] - val;
for(int i1 = 1; i1 <= n; i1++)
{
for(int i2 = i1 + r - 1; i2 <= min(2 * n, i1 + n); i2++)
{
dq.clear();
for(int j = 1; j <= 2 * m; j++)
{
v[j] = v[j - 1] + (aux[i2][j] - aux[i1 - 1][j]);
if(j >= c)
{
while(!dq.empty() && v[j - c] <= v[dq.back()])
dq.pop_back();
dq.push_back(j - c);
if(dq.front() == j - m)
dq.pop_front();
if(v[j] - v[dq.front()] >= 0)
return 1;
}
}
}
}
return 0;
}
int main()
{
fin >> n >> m >> r >> c;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
fin >> mat[i][j];
mat[i + n][j] = mat[i][j];
mat[i][j + n] = mat[i][j];
mat[i + n][j + n] = mat[i][j];
}
}
double st = 0, dr = 100000, ans = 0;
while(st + eps <= dr)
{
double med = (st + dr) / 2;
if(check(med))
{
ans = med;
st = med;
}
else
dr = med;
}
fout << fixed << setprecision(3) << ans;
return 0;
}