fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int INF = 1e9;
  9. const ll LINF = 1e18;
  10.  
  11. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. if (a < b) a = b;
  14. }
  15.  
  16. const int N = 1e3 + 5;
  17.  
  18. // Đây không hẳn là một bài cơ bản như trong đề bài nhắc đến
  19. // Nếu so với bài QBRECT - tìm hình chữ nhật lớn nhất thì có thể nói các bài toán đếm đều khó chịu hơn so với các bài toán tìm min/max
  20. // Tương tự ở bài này ta cũng sẽ giải quyết bài toán theo từng hàng
  21. // Khi xét đến hàng thứ i cần tính được các thông tin:
  22. // h[j] = độ cao của cột thứ j = độ dài đoạn con liên tiếp dài nhất kết thúc tại a(i, j) và chỉ chứa toàn số 1
  23. // l[j] = phần tử gần nhất bên trái < h[j]
  24. // Gọi dp[j] = Số hình chữ nhật thoả mãn chỉ chứa toàn số 1 và có ô góc phải dưới là ô a(i, j)
  25. // Để tính dp[j] ta cũng sẽ xét 2 trường hợp:
  26. // Trường hợp 1: cột j đóng vai trò là min (cột nhỏ nhất)
  27. // - Chọn chiều cao của cột thứ j: 1 -> h[j]
  28. // - Chọn các cột ở trước để lấp vào: l[j] + 1 -> j
  29. // => Tổng số cách = h[j] * (j - l[j])
  30. // Trường hợp 2: cột j không đóng vai trò là min
  31. // Chiều cao các cột từ l[j] + 1 đến j sẽ phụ thuộc vào chiều cao của cột ở trước đó đóng vai trò là min
  32. // => dp[l[j]]
  33. int n, m;
  34. int a[N][N];
  35.  
  36. int h[N];
  37. int l[N];
  38. ll dp[N];
  39.  
  40. ll solve(int i) {
  41. for (int j = 1; j <= m; j++) {
  42. if (a[i][j] == 0) h[j] = 0;
  43. else h[j]++;
  44. }
  45.  
  46. vector<int> st;
  47. for (int j = 1; j <= m; j++) {
  48. while (!st.empty() && h[st.back()] >= h[j]) st.pop_back();
  49. l[j] = st.empty() ? 0 : st.back();
  50. st.push_back(j);
  51. }
  52.  
  53. for (int j = 1; j <= m; j++) {
  54. dp[j] = h[j] * (j - l[j]); // Trường hợp 1
  55. dp[j] += dp[l[j]]; // Trường hợp 2
  56. }
  57.  
  58. ll ans = 0;
  59. for (int j = 1; j <= m; j++) ans += dp[j];
  60.  
  61. return ans;
  62. }
  63.  
  64. int main() {
  65. ios::sync_with_stdio(false);
  66. cin.tie(nullptr);
  67. cin >> n >> m;
  68.  
  69. for (int i = 1; i <= n; i++) {
  70. string s; cin >> s;
  71. s = ' ' + s;
  72. for (int j = 1; j <= m; j++) {
  73. a[i][j] = s[j] - '0';
  74. }
  75. }
  76.  
  77. ll ans = 0;
  78. for (int i = 1; i <= n; i++) {
  79. ans += solve(i);
  80. }
  81.  
  82. cout << ans << '\n';
  83. }
Success #stdin #stdout 0.01s 5620KB
stdin
4 3
111
101
111
001
stdout
24