Cod sursa(job #2887476)

Utilizator T_george_TGeorge Teodorescu T_george_T Data 9 aprilie 2022 18:30:40
Problema Coduri Huffman Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <set>

using namespace std;

const int NMAX = 1004;

ifstream in("dreptunghiuri5.in");
ofstream out("dreptunghiuri5.out");

int down[NMAX][NMAX], a[NMAX][NMAX], r[NMAX][NMAX], l[NMAX][NMAX];
stack<int> s;

int main() {
    int n, m, ans = 0;
    in >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            in >> a[i][j];

    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 0)
                down[i][j] = down[i + 1][j] + 1;

    for (int i = 1; i <= n; i++) {
        set<pair<int, int>> st;
        for (int j = 1; j <= m; j++) {
            while (!s.empty() && down[i][s.top()] > down[i][j]) {
                r[i][s.top()] = j - 1;
                s.pop();
            }
            s.push(j);
        }
        while (!s.empty()) {
            r[i][s.top()] = m;
            s.pop();
        }
        for (int j = m; j >= 1; j--) {
            while (!s.empty() && down[i][s.top()] > down[i][j]) {
                l[i][s.top()] = j + 1;
                s.pop();
            }
            s.push(j);
        }
        while (!s.empty()) {
            l[i][s.top()] = 1;
            s.pop();
        }
        for (int j = 1; j <= m; j++) {
            if (a[i][j]==0 && (a[i-1][j]==1 || (i==1) || (r[i - 1][j] - l[i - 1][j] < r[i][j] - l[i][j])) &&  st.find({l[i][j], r[i][j] - l[i][j] + 1}) == st.end()) {
                ans++;
                st.insert({l[i][j], r[i][j] - l[i][j] + 1});
            }
        }

    }
    out << ans;
    return 0;
}