Pagini recente » Cod sursa (job #1956640) | Cod sursa (job #2112028) | Cod sursa (job #706225) | Cod sursa (job #1840967) | Cod sursa (job #1068534)
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
const int Nmax = 302;
int N, M, R, C;
int deck[Nmax];
int A[Nmax][Nmax];
long long sum[Nmax][Nmax];
long long sumCol[Nmax];
int valid( int cost )
{
for ( int i = 1; i <= 2 * N; ++i )
{
for ( int j = i + R - 1; j - i < N && j <= 2 * N; ++j )
{
for ( int k = 1; k <= 2 * M; ++k )
{
sumCol[k] = sumCol[k - 1] + sum[j][k] - sum[i - 1][k] - 1LL * cost * ( j - i + 1 );
}
int front = 1, back = 0;
for ( int k = C; k <= 2 * M; ++k )
{
while ( front <= back && sumCol[ deck[ back ] ] > sumCol[k - C] ) back--;
while ( front <= back && deck[ front ] < k - M ) front++;
deck[ ++back ] = k - C;
if ( sumCol[k] >= sumCol[ deck[ front ] ] )
return 1;
}
}
}
return 0;
}
int cautare_binara()
{
int st = 0;
int dr = 100001 * 1000;
int sol = 0;
int m;
while ( st <= dr )
{
m = ( st + dr ) / 2;
if ( valid( m ) )
{
st = m + 1;
sol = m;
}
else
{
dr = m - 1;
}
}
return sol;
}
const int DIM_BUFF = ( 1 << 20 );
char buffer[DIM_BUFF];
int position = DIM_BUFF;
char GetChar()
{
if ( position == DIM_BUFF )
{
fread( buffer, 1, DIM_BUFF, stdin );
position = 0;
}
return buffer[ position++ ];
}
int rd()
{
int nr = 0;
char c;
do
{
c = GetChar();
} while ( !isdigit( c ) );
do
{
nr = nr * 10 + ( c - '0' );
c = GetChar();
} while ( isdigit( c ) );
return nr;
}
int main()
{
freopen("balans.in", "r", stdin);
ofstream g("balans.out");
N = rd(); M = rd(); R = rd(); C = rd();
for ( int i = 1; i <= N; ++i )
for ( int j = 1; j <= M; ++j )
{
A[i][j] = rd();
A[i][j] *= 1000;
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 * N; ++j )
{
sum[i][j] = sum[i - 1][j] + A[i][j];
}
}
g << fixed << setprecision( 3 );
g << (double)cautare_binara() / 1000.0;
return 0;
}