Pagini recente » Cod sursa (job #63665) | Cod sursa (job #1729187) | Cod sursa (job #974532) | Cod sursa (job #2887476)
#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;
}