Pagini recente » Cod sursa (job #125862) | Cod sursa (job #2063175) | Cod sursa (job #1257791) | Cod sursa (job #1924969) | Cod sursa (job #1941851)
#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];
LL N, M;
LL P, Q;
LL sc[MAX][MAX];
LL v[MAX];
LL maxim;
deque<LL> D;
void Read();
LL BinarySearch();
bool Check( LL v );
bool Deque( vector<LL>& s );
int main()
{
Read();
fout << fixed << setprecision(3) << BinarySearch() / 1000. << '\n';
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> N >> M >> P >> Q;
for ( LL i = 1; i <= N; ++i )
for ( LL j = 1; j <= M; ++j )
fin >> a[i][j];
for ( LL i = 1; i <= N; ++i )
for ( LL j = 1; j <= M; ++j )
{
a[i + N][j] = a[i][j + M] = a[i + N][j + M] = a[i][j] = a[i][j] * 1000;
maxim = max( maxim, a[i][j] );
}
N *= 2, M *= 2;
/* for ( LL i = 1; i <= N; ++i )
{
for ( LL 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 ) / 2LL;
if ( Check(mij) )
{
r = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
return r;
}
bool Check( LL v )
{
LL i1, i2, i, j;
bool ok{false};
vector<LL> s(M + 1);
for ( i = 1; i <= N; ++i )
for ( j = 1; j <= M; ++j )
{
a[i][j] -= v;
sc[i][j] = sc[i - 1][j] + a[i][j];
}
for ( i1 = 1; i1 <= (N >> 1) && !ok; ++i1 )
for ( i2 = i1 + P - 1; i2 <= i1 + ( N >> 1 ) && !ok; ++i2 )
{
for ( j = 1; j <= M; ++j )
s[j] = s[j - 1] + ( sc[i2][j] - sc[i1 - 1][j] );
if ( Deque(s) )
ok = true;
}
for ( i = 1; i <= N; ++i )
for ( j = 1; j <= M; ++j )
a[i][j] += v;
return ok;
}
bool Deque( vector<LL>& s )
{
D.clear();
LL 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;
}