Pagini recente » Cod sursa (job #1910837) | Cod sursa (job #2770729) | Cod sursa (job #3170617) | Cod sursa (job #3123651) | Cod sursa (job #1941758)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
const int MAX = 310;
using LL = long long;
LL a[MAX][MAX];
int N, M;
int P, Q;
LL sc[MAX][MAX];
LL v[MAX];
LL maxim;
void Read();
LL BinarySearch();
bool Check( LL v );
bool Deque( vector<LL>& s );
int main()
{
Read();
fout << fixed << setprecision(3) << BinarySearch() / 10000. << '\n';
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> N >> M >> P >> Q;
for ( int i = 1; i <= N; ++i )
for ( int j = 1; j <= M; ++j )
fin >> 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] = a[i][j] * 10000;
maxim = max( maxim, a[i][j] );
}
N *= 2, M *= 2;
for ( int i = 1; i <= N; ++i )
{
for ( int j = 1; j <= M; ++j )
{
sc[i][j] = sc[i - 1][j] + a[i][j];
// fout << a[i][j] << ' ';
}
// fout << '\n';
}
}
LL BinarySearch()
{
LL st = 1, dr = maxim, mij, r{0};
while ( st <= dr )
{
mij = st + ( dr - st ) / 2;
if ( Check(mij) )
{
r = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
return r;
}
bool Check( LL v )
{
int i1, i2, j;
bool ok{false};
vector<LL> s(M + 1, 0);
for ( i1 = 1; i1 <= N && !ok; ++i1 )
for ( i2 = i1 + P - 1; i2 <= N && !ok; ++i2 )
{
for ( j = 1; j <= M; ++j )
s[j] = s[j - 1] + ( sc[i2][j] - sc[i1 - 1][j] - ( ( i2 - i1 + 1 ) * v ) );
if ( Deque(s) )
ok = true;
}
return ok;
}
bool Deque( vector<LL>& s )
{
deque<int> D;
int i;
for ( i = Q; i <= M; ++i )
{
while ( !D.empty() && s[i - Q] <= s[D.back()] )
D.pop_back();
D.push_back(i - Q);
if ( s[i] - s[D.front()] >= 0 )
return true;
}
return false;
}