fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 4e2;
  12. const int max_ai = maxn * maxn;
  13.  
  14. int n, m, a[maxn + 10][maxn + 10], lst[maxn + 10][max_ai + 10], mx = 0, cnt[max_ai + 10];
  15. int mx_1[maxn + 10][maxn + 10][maxn + 10], mx_2[maxn + 10][maxn + 10][maxn + 10];
  16. bool check[maxn + 10][maxn + 10][maxn + 10];
  17. vector<int> val;
  18. vector<ii> pos[max_ai + 10];
  19. ll ans = 0;
  20.  
  21. int get_id(int x)
  22. {
  23.     return lower_bound(val.begin(), val.end(), x) - val.begin();
  24. }
  25.  
  26. int main()
  27. {
  28.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  29.     if (fopen("TABLE3.INP", "r"))
  30.     {
  31.         freopen("TABLE3.INP", "r", stdin);
  32.         freopen("TABLE3.OUT", "w", stdout);
  33.     }
  34.  
  35.     cin >> n >> m;
  36.     for (int i = 1; i <= n; i++)
  37.         for (int j = 1; j <= m; j++)
  38.         {
  39.             cin >> a[i][j];
  40.             val.push_back(a[i][j]);
  41.         }
  42.     sort(val.begin(), val.end());
  43.     val.resize(unique(val.begin(), val.end()) - val.begin());
  44.     for (int i = 1; i <= n; i++)
  45.         for (int j = 1; j <= m; j++)
  46.             a[i][j] = get_id(a[i][j]);
  47.     for (int k = 1; k <= m; k++)
  48.     {
  49.         for (int i = 1; i <= n; i++)
  50.         {
  51.             for (int j = i; j >= 1; j--)
  52.                 mx_1[k][i][j] = max(mx_1[k][i][j + 1], lst[j][a[i][k]]);
  53.             for (int j = i; j <= n; j++)
  54.                 mx_2[k][i][j] = max(mx_2[k][i][j - 1], lst[j][a[i][k]]);
  55.         }
  56.         for (int i = 1; i <= n; i++)
  57.             lst[i][a[i][k]] = k;
  58.     }
  59.     for (int k = 1; k <= m; k++)
  60.     {
  61.         for (int j = 1; j <= n; j++)
  62.             for (int i = j + 1; i <= n; i++)
  63.                 mx_1[k][i][j] = max(mx_1[k][i][j], mx_1[k][i - 1][j]);
  64.         for (int j = n; j >= 1; j--)
  65.             for (int i = j - 1; i >= 1; i--)
  66.                 mx_2[k][i][j] = max(mx_2[k][i][j], mx_2[k][i + 1][j]);
  67.     }
  68.     for (int k = 1; k <= m; k++)
  69.     {
  70.         for (int i = 1; i <= n; i++)
  71.         {
  72.             check[k][i][i] = 1;
  73.             cnt[a[i][k]]++;
  74.             for (int j = i + 1; j <= n; j++)
  75.             {
  76.                 cnt[a[j][k]]++;
  77.                 check[k][i][j] = check[k][i][j - 1] && cnt[a[j][k]] == 1;
  78.             }
  79.             for (int j = i; j <= n; j++)
  80.                 cnt[a[j][k]]--;
  81.         }
  82.     }
  83.     for (int i = 1; i <= n; i++)
  84.         for (int j = i; j <= n; j++)
  85.         {
  86.             mx = 0;
  87.             for (int k = 1; k <= m; k++)
  88.             {
  89.                 if (!check[k][i][j])
  90.                     mx = k;
  91.                 mx = max(mx, max(mx_1[k][j][i], mx_2[k][i][j]));
  92.                 ans = max(ans, 1ll * (j - i + 1) * (k - mx));
  93.             }
  94.         }
  95.     cout << ans;
  96. }
  97.  
Success #stdin #stdout 0.01s 9132KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/MOESnz
language:
C++14 (gcc 8.3)
created:
22 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!