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. int main()
  12. {
  13.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  14.     if (fopen("TABLE3.INP", "r"))
  15.     {
  16.         freopen("TABLE3.INP", "r", stdin);
  17.         freopen("TABLE3.OUT", "w", stdout);
  18.     }
  19.  
  20.     int n, m;
  21.     cin >> n >> m;
  22.     vector<vector<int>> a(n + 1, vector<int>(m + 1));
  23.     vector<int> vals;
  24.     vals.reserve(n * m);
  25.     for (int i = 1; i <= n; ++i)
  26.         for (int j = 1; j <= m; ++j)
  27.         {
  28.             cin >> a[i][j];
  29.             vals.push_back(a[i][j]);
  30.         }
  31.     sort(vals.begin(), vals.end());
  32.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  33.     auto get_id = [&](int x){
  34.         return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
  35.     };
  36.     int V = (int)vals.size();
  37.     for (int i = 1; i <= n; ++i)
  38.         for (int j = 1; j <= m; ++j)
  39.             a[i][j] = get_id(a[i][j]);
  40.  
  41.     auto idx = [&](int i, int j)->int { return i * (n + 1) + j; };
  42.     int SZ = (n + 1) * (n + 1);
  43.  
  44.     vector<int> mx1(SZ, 0), mx2(SZ, 0);
  45.     vector<int> mx_block(SZ, 0);
  46.     vector<char> check(SZ, 0);
  47.  
  48.     unordered_map<long long, int> lastpos;
  49.     lastpos.reserve((size_t)n * m * 2 + 10);
  50.  
  51.     ll ans = 0;
  52.  
  53.     vector<int> cnt(V, 0);
  54.     vector<int> seen; seen.reserve(n);
  55.  
  56.     const long long MUL = 1000LL;
  57.  
  58.     for (int k = 1; k <= m; ++k)
  59.     {
  60.         for (int r = 1; r <= n; ++r)
  61.         {
  62.             int cur = 0;
  63.             for (int s = r; s >= 1; --s)
  64.             {
  65.                 long long key = (long long)a[r][k] * MUL + s;
  66.                 auto it = lastpos.find(key);
  67.                 int last = (it == lastpos.end() ? 0 : it->second);
  68.                 if (last > cur) cur = last;
  69.                 mx1[idx(r, s)] = cur;
  70.             }
  71.         }
  72.         for (int r = 1; r <= n; ++r)
  73.         {
  74.             int cur = 0;
  75.             for (int s = r; s <= n; ++s)
  76.             {
  77.                 long long key = (long long)a[r][k] * MUL + s;
  78.                 auto it = lastpos.find(key);
  79.                 int last = (it == lastpos.end() ? 0 : it->second);
  80.                 if (last > cur) cur = last;
  81.                 mx2[idx(r, s)] = cur;
  82.             }
  83.         }
  84.  
  85.         for (int j = 1; j <= n; ++j)
  86.             for (int i = j + 1; i <= n; ++i)
  87.                 if (mx1[idx(i - 1, j)] > mx1[idx(i, j)])
  88.                     mx1[idx(i, j)] = mx1[idx(i - 1, j)];
  89.  
  90.         for (int j = n; j >= 1; --j)
  91.             for (int i = j - 1; i >= 1; --i)
  92.                 if (mx2[idx(i + 1, j)] > mx2[idx(i, j)])
  93.                     mx2[idx(i, j)] = mx2[idx(i + 1, j)];
  94.  
  95.         for (int i = 1; i <= n; ++i)
  96.         {
  97.             seen.clear();
  98.             bool ok = true;
  99.             for (int j = i; j <= n; ++j)
  100.             {
  101.                 int v = a[j][k];
  102.                 if (cnt[v] == 0) seen.push_back(v);
  103.                 cnt[v]++;
  104.                 if (cnt[v] > 1) ok = false;
  105.                 check[idx(i, j)] = ok ? 1 : 0;
  106.             }
  107.             for (int v : seen) cnt[v] = 0;
  108.         }
  109.  
  110.         for (int i = 1; i <= n; ++i)
  111.         {
  112.             for (int j = i; j <= n; ++j)
  113.             {
  114.                 int &mx = mx_block[idx(i, j)];
  115.                 if (!check[idx(i, j)]) mx = k;
  116.                 if (mx1[idx(j, i)] > mx) mx = mx1[idx(j, i)];
  117.                 if (mx2[idx(i, j)] > mx) mx = mx2[idx(i, j)];
  118.                 ll width = k - mx;
  119.                 if (width > 0)
  120.                 {
  121.                     ll area = 1ll * (j - i + 1) * width;
  122.                     if (area > ans) ans = area;
  123.                 }
  124.             }
  125.         }
  126.  
  127.         for (int r = 1; r <= n; ++r)
  128.         {
  129.             long long key = (long long)a[r][k] * MUL + r;
  130.             lastpos[key] = k;
  131.         }
  132.     }
  133.  
  134.     cout << ans;
  135. }
  136.  
Success #stdin #stdout 0.09s 375880KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/bcrXKR
language:
C++14 (gcc 8.3)
created:
3 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!