Pagini recente » Cod sursa (job #3352051) | Cod sursa (job #1143443) | Cod sursa (job #1509479) | Borderou de evaluare (job #353730) | Cod sursa (job #3313001)
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
const int Nmax = 155 * 2;
long long mat[Nmax][Nmax], sp_col[Nmax], n, m, r, c;
int i1, i2;
bool verif( int x )
{
int sp[Nmax];
int i;
sp[0] = 0;
for ( i = 1; i <= m; ++i )
sp[i] = (int)sp_col[i] - x * (i2 - i1 + 1);
for ( i = 1; i <= m; ++i )
{
sp[i] += sp[i - 1];
// if ( x == 11.5)
// fout << sp[i] << " ";
}
//if ( x == 11.5)
// fout << endl;
int sp_min = 0;
int l = m / 2;
deque <int> deq;
for ( i = c; i <= m; ++i )
{
if (!deq.empty() && deq.front() < i - l )
deq.pop_front();
while ( deq.empty() == false && sp[deq.back()] > sp[i - c] )
deq.pop_back();
deq.push_back( i - c );
sp_min = sp[deq.front()];
if ( sp[i] - sp_min >= 0 )
{
// if ( x == 11.5)
// fout << " secv buna are i = " << i << " si capat st = " << deq.front() + 1 << endl;
return true;
}
}
return false;
}
int calc()
{
int st = 0, dr = 1e8 + 25, mij, sol = 0;
while ( st <= dr )
{
mij = (st + dr) / 2;
if ( verif(mij) )
{
sol = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
return sol;
}
void reset()
{
int i;
for ( i = 1; i <= m; ++i )
sp_col[i] = 0;
}
int main()
{
int i, j;
fin >> n >> m >> r >> c;
for ( i = 1; i <= n; ++i )
for ( j = 1; j <= m; ++j )
{
fin >> mat[i][j];
mat[i][j] *= 1000;
mat[i + n][j] = mat[i + n][j + n] = mat[i][j + n] = mat[i][j];
}
n = 2 * n;
m = 2 * m;
int sol = 0;
for ( i1 = 1; i1 <= n - r + 1; ++i1)
{
reset();
for ( i = i1; i < i1 + r - 1; ++i )
for ( j = 1; j <= m; ++j )
sp_col[j] += mat[i][j];
for ( i2 = i1 + r - 1; i2 <= n && i2 - i1 + 1 <= n / 2; ++i2 )
{
for ( j = 1; j <= m; ++j )
sp_col[j] += mat[i2][j];
// if (i1 == 3 && i2 == 4)
// fout << "verif = " << verif(11.5) << endl;
sol = max(sol, calc());
}
}
fout << fixed << setprecision(3) << 1.0 * sol / 1000 << '\n';
return 0;
}