Advertisement
MinhNGUYEN2k4

Untitled

Sep 13th, 2021
905
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 2005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, m;
  28. int a[1005][1005];
  29. int h[1005];
  30. int pre[1005], nex[1005], x[1005], y[1005];
  31.  
  32. void readfile()
  33. {
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0);cout.tie(0);
  36.     if (fopen(Task".inp","r"))
  37.     {
  38.         freopen(Task".inp","r",stdin);
  39.         //freopen(Task".out","w",stdout);
  40.     }
  41.     cin >> n >> m;
  42.     for(int i=1; i<=n; i++){
  43.         for(int j=1; j<=m; j++){
  44.             cin >> a[i][j];
  45.             //cout << a[i][j] << " \n"[j==m];
  46.         }
  47.     }
  48. }
  49.  
  50. void proc()
  51. {
  52.     int ans = 1;
  53.     for(int day=1; day <= n; day++){
  54.         for(int i=1; i<=m; i++){
  55.             if (day==1) h[i]=1;
  56.             else{
  57.                 if (a[day][i]==a[day-1][i]) h[i] = 1;
  58.                 else h[i]++;
  59.             }
  60.         }
  61.         h[0] = minf;
  62.         stack<int> st;
  63.         st.push(0);
  64.         for(int i=1; i<=m; i++){
  65.             while (st.size() && h[st.top()] >= h[i]) st.pop();
  66.             pre[i] = st.top();
  67.             st.push(i);
  68.         }
  69.         while (st.size()) st.pop();
  70.         h[m+1] = minf;
  71.         st.push(m+1);
  72.         for(int i=m; i>=1; i--){
  73.             while (st.size() && h[st.top()] >= h[i]) st.pop();
  74.             nex[i] = st.top();
  75.             st.push(i);
  76.         }
  77.         x[1] = 1;
  78.         for(int i=2; i<=m; i++){
  79.             x[i] = (a[day][i]!=a[day][i-1] ? x[i-1] : i);
  80.         }
  81.         y[m] = m;
  82.         for(int i=m-1; i>=1; i--){
  83.             y[i] = (a[day][i]!=a[day][i+1] ? y[i+1] : i);
  84.         }
  85.         int res=0;
  86.  
  87.         for(int i=1; i<=m; i++) ans = max(ans, h[i]*(min(y[i],nex[i]-1)-max(x[i],pre[i]+1)+1));
  88.     }
  89.     cout << ans;
  90. }
  91.  
  92. signed main()
  93. {
  94.     readfile();
  95.     proc();
  96.     return 0;
  97. }
  98.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement