fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define li pair<long long , int>
  10. #define iii pair<pair<int , int> , int>
  11. #define db double
  12. #define onBit(mask , i) (mask | (1 << i))
  13. #define offBit(mask , i) (mask & (~(1 << i)))
  14.  
  15. const long long MOD = 1e9 + 7;
  16. const int INF = 8e7;
  17. const int N = 1e6 + 7;
  18. vector<char> a[N];
  19. int n , m , BIT[N];
  20.  
  21. struct gv{
  22.     int l , r;
  23.     char c;
  24. };
  25.  
  26. vector<gv> cand;
  27.  
  28. bool cmp(gv x , gv y){
  29.     if (x.c != y.c) return x.c < y.c;
  30.     if (x.l != y.l) return x.l < y.l;
  31.     return x.r > y.r;
  32. }
  33.  
  34. void ktao(){
  35.     for (int u = 0 ; u < m ; ++u){
  36.         int i = 1;
  37.         while (i <= n){
  38.             int j = i;
  39.             while (j < n && a[j + 1][u] == a[i][u]) ++j;
  40.             gv e;
  41.             e.l = i , e.r = j , e.c = a[i][u];
  42.             cand.push_back(e);
  43.             i = j + 1;
  44.         }
  45.     }
  46.     sort(cand.begin() , cand.end() , cmp);
  47. }
  48.  
  49. void inp(){
  50.     cin >> n >> m;
  51.     for (int i = 1 ; i <= n ; ++i){
  52.         for (int j = 1 ; j <= m ; ++j){
  53.             char c;
  54.             cin >> c;
  55.             a[i].push_back(c);
  56.         }
  57.     }
  58.     ktao();
  59. }
  60.  
  61. void update(int x , int val){
  62.     while (x > 0){
  63.         BIT[x] += val;
  64.         x -= x & -x;
  65.     }
  66. }
  67.  
  68. int get(int x){
  69.     int res = 0;
  70.     while (x <= n){
  71.         res += BIT[x];
  72.         x += x & -x;
  73.     }
  74.     return res;
  75. }
  76.  
  77. int nl(int l , int r){
  78.     memset(BIT , 0 , sizeof BIT);
  79.     int res = 0;
  80.     for (int i = l ; i <= r ; ++i){
  81.         int u = cand[i].l , v = cand[i].r;
  82.         int tmp = get(v) + 1;
  83.         res = max(res , (v - u + 1) * tmp);
  84.         update(v , 1);
  85.     }
  86.     return res;
  87. }
  88.  
  89. void solve(){
  90.     int i = 0;
  91.     int res = 0;
  92.     while (i < cand.size()){
  93.         int j = i;
  94.         while (j < cand.size() - 1 && cand[i].c == cand[j + 1].c) ++j;
  95.         res = max(res , nl(i , j));
  96.         i = j + 1;
  97.     }
  98.     cout << res;
  99. }
  100.  
  101. int main(){
  102. //    freopen("xhmax.inp" , "r" , stdin);
  103. //    freopen("xhmax.out" , "w" , stdout);
  104.     faster;
  105.     inp();
  106.     solve();
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0.01s 27456KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/3obhTl
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!