Advertisement
ivnikkk

Untitled

Dec 24th, 2021
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.16 KB | None | 0 0
  1. #include <vector>
  2. #include<iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13. #include <random>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. using namespace std;
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. #define endl "\n"
  22. #define all(a) a.begin(), a.end()
  23. #define allr(a) a.rbegin(), a.rend()
  24. #define pb push_back
  25. #define F first
  26. #define S second
  27. ll inf = 1e18;
  28. const ll c = 600;
  29. struct point {
  30. ld x, y;
  31. };
  32.  
  33. struct Vector {
  34. ld x, y;
  35. Vector(ld x_ = 0, ld y_ = 0) {
  36. x = x_;
  37. y = y_;
  38. }
  39. Vector(point& a, point& b) {
  40. x = b.x - a.x;
  41. y = b.y - a.y;
  42. }
  43. };
  44. const ll mod = 1e9 + 7;
  45. template<typename T>
  46. T SUM(T x) {
  47. return x;
  48. }
  49. template<typename T, typename... Ts>
  50. T SUM(T x, Ts... y) {
  51. T res = x + SUM(y...);
  52. if (res >= mod)
  53. res -= mod;
  54. return res;
  55. }
  56. template<typename T, typename... Ts>
  57. T sub(T x, Ts... y) {
  58. return SUM(x, mod - SUM(y...));
  59. }
  60. template<typename T>
  61. T proiz(T x) {
  62. return x;
  63. }
  64. template<typename T, typename... Ts>
  65. T proiz(T x, Ts... y) {
  66. return (x * 1ll * proiz(y...)) % mod;
  67. }
  68. template<typename T, typename... Ts>
  69. void prisvoenie_proiz(T& x, Ts... y) {
  70. x = proiz(x, y...);
  71. }
  72. ll bin(ll a, ll deg) {
  73. ll r = 1;
  74. while (deg) {
  75. if (deg & 1)
  76. prisvoenie_proiz(r, a);
  77. deg >>= 1;
  78. prisvoenie_proiz(a, a);
  79. }
  80. return r;
  81. }
  82. ll inv(ll x) {
  83. return bin(x, mod - 2);
  84. }
  85. void solve() {
  86. ll n, m;
  87. cin >> m >> n;
  88. vector<vector<ll>> a(m, vector<ll>(n));
  89. for (ll i = 0; i < m; i++) {
  90. for (ll j = 0; j < n; j++) {
  91. cin >> a[i][j];
  92. }
  93. }
  94. vector <ll> h(n + 2,0);
  95. ll mxans = -inf;
  96. for (ll j = 0; j < m; j++) {
  97. h[0] = -inf;
  98. h[n + 1] = -inf;
  99. for (ll i = 1; i <= n; i++) {
  100. if (!a[j][i - 1]) {
  101. h[i]++;
  102. }
  103. else {
  104. h[i] = 0;
  105. }
  106. }
  107. vector <ll> stack1(1, 0), stack2(1, n + 1), ans1(n + 2), ans2(n + 2);
  108. for (ll i = 1; i < n + 2; i++) {
  109. while (h[stack1.back()] > h[i]) {
  110. ans1[stack1.back()] = i;
  111. stack1.pop_back();
  112. }
  113. stack1.push_back(i);
  114. }
  115. for (ll i = n + 1; i >= 1; i--) {
  116. while (h[stack2.back()] > h[i]) {
  117. ans2[stack2.back()] = i;
  118. stack2.pop_back();
  119. }
  120. stack2.push_back(i);
  121. }
  122. ll anss = -inf;
  123. for (ll i = 1; i <= n; i++) {
  124. anss = max(anss, h[i] * (ans1[i] - 1 - (ans2[i] + 1) + 1));
  125. }
  126. mxans = max(anss, mxans);
  127. }
  128. cout << mxans << endl;
  129. }
  130. signed main() {
  131. ios_base::sync_with_stdio(false);
  132. cin.tie(nullptr);
  133. ll t = 1;
  134. //cin >> t;
  135. while (t--) {
  136. solve();
  137. }
  138. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement