trafik

Untitled

Oct 10th, 2022
833
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define ld long double
  5. #define len(v) (int)v.size()
  6. #define all(v) v.begin(), v.end()
  7. #define rall(v) v.rbegin(), v.rend()
  8. #define pii pair<int, int>
  9. #define vi vector<int>
  10. #define vii vector<vector<int>>
  11. #define vpii vector<pair<int, int>>
  12. #define ull unsigned long long
  13. //#define int long long
  14. //#define ll ull
  15. const int N = 1e6 + 1;
  16. const int maxn = 5e6 + 10;
  17. const int C = 20;
  18. const int logn = 20;
  19. const ll inf = 1e9;
  20. const ll mod = 1e9 + 7;
  21. const int M = 1e9;
  22. const ull M2 = 998244353;
  23. const ld eps = 1e-6;
  24. using namespace std;
  25.  
  26. template<class T>
  27. istream &operator>>(istream &in, vector<T> &a) {
  28.     for (auto &i : a)
  29.         in >> i;
  30.     return in;
  31. }
  32.  
  33. template<class T>
  34. ostream &operator<<(ostream &out, vector<T> &a) {
  35.     for (auto &i : a)
  36.         out << i << ' ';
  37.     return out;
  38. }
  39.  
  40. ll gist(vector<int>& b) {
  41.     int n = len(b);
  42.     vector<pii> s;
  43.     s.emplace_back(0, -1);
  44.     ll res = 0;
  45.     for (int i = 0; i <= n; ++i) {
  46.         int h;
  47.         if (i < n) h = b[i];
  48.         else h = 0;
  49.         int x = i;
  50.  
  51.         while (h <= s.back().second) {
  52.             x = s.back().first;
  53.             int hprev = s.back().second;
  54.             s.pop_back();
  55.             ll area = 1ll * hprev * (i - x);
  56.             if (area > res) res = area;
  57.         }
  58.         s.emplace_back(x, h);
  59.     }
  60.     return res;
  61. }
  62.  
  63. void solve() {
  64.     int n, m;
  65.     cin >> n >> m;
  66.  
  67.     vector<vector<int>> a(n, vector<int>(m));
  68.     for (auto &i: a) {
  69.         for (auto& el : i) {
  70.             int x; cin >> x;
  71.             el = (x ? 0 : 1);
  72.         }
  73.     }
  74.     if (n == 1 && m == 1 && a[0][0] == 1) {
  75.         cout << "1";
  76.         return;
  77.     }
  78.     vector<vector<int>> p(n, vector<int>(m));
  79.     p = a;
  80.     for (int i = 0; i < n; ++i) {
  81.         for (int j = 0; j < m; ++j) {
  82.             if (p[i][j] && i > 0)
  83.                 p[i][j] += p[i - 1][j];
  84.         }
  85.     }
  86.     ll ans = 0;
  87.     for (int i = 0; i < n; ++i) {
  88.         ans = max(ans, gist(p[i]));
  89.     }
  90.     cout << ans;
  91.  
  92. }
  93.  
  94. signed main() {
  95.     ios::sync_with_stdio(false);
  96.     cin.tie(nullptr);
  97.     cout.tie(nullptr);
  98.  
  99.     int T = 1;
  100.     //cin >> T;
  101.     while (T--)
  102.         solve();
  103. }
Advertisement
Add Comment
Please, Sign In to add comment