Cod sursa(job #3313002)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 1 octombrie 2025 18:09:00
Problema Balans Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
const long long Nmax = 155 * 2;
long long mat[Nmax][Nmax], sp_col[Nmax], n, m, r, c;
long long i1, i2;
bool verif( long long x )
{
    long long sp[Nmax];
    long long i;
    sp[0] = 0;
    for ( i = 1; i <= m; ++i )
        sp[i] = (long long)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;
    long long sp_min = 0;
    long long l = m / 2;
    deque <long long> 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;
}
long long calc()
{
    long long 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()
{
    long long i;
    for ( i = 1; i <= m; ++i )
        sp_col[i] = 0;
}
int main()
{
    long long 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;
    long long 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;
}