Cod sursa(job #2331649)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 29 ianuarie 2019 19:27:36
Problema Balans Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>
#include <iomanip>
#include <deque>
 
#define lint long long int
using namespace std;
 
const int NMAX = 155;
 
int n, m, r, c;
int mat[2 * NMAX][2 * NMAX];
 
lint s_part[2 * NMAX];
deque <int> coada;
 
bool exists (int x) {
    int j, k;
    lint sum;
 
    for (int i = 1; i <= 2 * n; ++ i) {
        for (k = 1; k <= 2 * m; ++ k)
            s_part[k] = 0;
 
        for (j = i; j <= 2 * n && j <= i + n - 1; ++ j) {
            sum = 0;
            for (k = 1; k <= 2 * m; ++ k) {
                sum += (mat[j][k] - x);
                s_part[k] += sum;
            }
 
            if (j < i + r - 1)
                continue ;
 
            coada.clear();
 
            for (k = 1; k <= 2 * m; ++ k) {
                while (!coada.empty() && coada.front() < k - n)
                    coada.pop_front();
 
                if (k >= c) {
                    while (!coada.empty() && s_part[coada.back()] >= s_part[k - c])
                        coada.pop_back();
                    coada.push_back(k - c);
 
 
                    if (s_part[k] - s_part[coada.front()] >= 0)
                        return true;
                }
            }
        }
    }
 
    return false;
}
 
int main()
{
    ifstream cin("balans.in");
    ofstream cout("balans.out");
 
    cin >> n >> m >> r >> c;
 
    if (!r) r = 1;
    if (!c) c = 1;
 
    int j;
    for (int i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
            cin >> mat[i][j];
 
    for (int i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
            mat[i][j] *= 1000;
 
    for (int i = 1; i <= 2 * n; ++ i) {
        for (j = 1; j <= 2 * m; ++ j)
            mat[i][j] = mat[(i - 1) % n + 1][(j - 1) % m + 1];
    }
 
    /*int st = 1;
    int dr = 100000000;
    int ans = 0;
{1}
    int mijl;
    while (st <= dr) {
        mijl = (st + dr) >> 1;
{1}
        if (exists(mijl)) {
            ans = mijl;
            st = mijl + 1;
        }
        else
            dr = mijl - 1;
    }*/
 
    int ans = 0;
 
    int steps;
    for (steps = 0; exists((1 << steps)); ++ steps);
    -- steps;
 
    for (; steps >= 0; -- steps)
        if (exists(ans | (1 << steps)))
            ans |= (1 << steps);
 
    cout << fixed << setprecision(3) << ans / 1000 << '.' << setw(3) << setfill('0') << ans % 1000 << '\n';
 
    cin.close();
    cout.close();
    return 0;
}