fork download
copy 
  1. // FROM CHATGPT : cay qua khong AC duoc nen em moi lam lieu nha dung go em <(")
  2.  
  3. #pragma GCC optimize("Ofast,unroll-loops")
  4. #include <bits/stdc++.h>
  5. #define ll long long
  6. using namespace std;
  7.  
  8. int main(){
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.     if (fopen("TABLE3.INP","r")){
  12.         freopen("TABLE3.INP","r",stdin);
  13.         freopen("TABLE3.OUT","w",stdout);
  14.     }
  15.     int n,m;
  16.     if(!(cin>>n>>m)) return 0;
  17.     vector<vector<int>> a(n+1, vector<int>(m+1));
  18.     vector<int> vals; vals.reserve(n*m);
  19.     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>a[i][j]; vals.push_back(a[i][j]); }
  20.     sort(vals.begin(), vals.end());
  21.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  22.     auto get_id = [&](int x)->int{ return lower_bound(vals.begin(), vals.end(), x) - vals.begin(); };
  23.     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j] = get_id(a[i][j]);
  24.     int V = (int)vals.size();
  25.     int MULT = n+1;
  26.     int SZ = MULT * MULT;
  27.  
  28.     vector<int> mx1(SZ,0), mx2(SZ,0), mx_block(SZ,0);
  29.     ll ans = 0;
  30.  
  31.     const long long FLAT_LIMIT = 50000000LL;
  32.     bool use_flat = (1LL * V * MULT <= FLAT_LIMIT);
  33.     vector<int> lastpos_flat;
  34.     unordered_map<int,int> lastpos_map;
  35.     if(use_flat){ lastpos_flat.assign(V * MULT, 0); }
  36.     else { lastpos_map.reserve(n*m*2 + 10); }
  37.  
  38.     auto lastpos_get = [&](int v, int row)->int{
  39.         int key = v * MULT + row;
  40.         if(use_flat) return lastpos_flat[key];
  41.         auto it = lastpos_map.find(key);
  42.         return (it==lastpos_map.end()?0:it->second);
  43.     };
  44.     auto lastpos_set = [&](int v, int row, int val){
  45.         int key = v * MULT + row;
  46.         if(use_flat) lastpos_flat[key] = val;
  47.         else lastpos_map[key] = val;
  48.     };
  49.  
  50.     vector<int> last_in_col(V,0), prev_same(n+1,0), prefMax(n+1,0);
  51.  
  52.     for(int k=1;k<=m;k++){
  53.         fill(last_in_col.begin(), last_in_col.end(), 0);
  54.         for(int r=1;r<=n;r++){
  55.             int v = a[r][k];
  56.             prev_same[r] = last_in_col[v];
  57.             last_in_col[v] = r;
  58.             prefMax[r] = prefMax[r-1] > prev_same[r] ? prefMax[r-1] : prev_same[r];
  59.         }
  60.  
  61.         for(int r=1;r<=n;r++){
  62.             int cur = 0;
  63.             int base1 = r * MULT;
  64.             int vr = a[r][k];
  65.             for(int s=r;s>=1;--s){
  66.                 int last = lastpos_get(vr, s);
  67.                 if(last > cur) cur = last;
  68.                 mx1[base1 + s] = cur;
  69.             }
  70.         }
  71.         for(int r=1;r<=n;r++){
  72.             int cur = 0;
  73.             int base2 = r * MULT;
  74.             int vr = a[r][k];
  75.             for(int s=r;s<=n;++s){
  76.                 int last = lastpos_get(vr, s);
  77.                 if(last > cur) cur = last;
  78.                 mx2[base2 + s] = cur;
  79.             }
  80.         }
  81.  
  82.         for(int j=1;j<=n;j++){
  83.             int jm = j * MULT;
  84.             for(int i=j+1;i<=n;i++){
  85.                 int idx1 = (i-1)*MULT + j;
  86.                 int idx2 = i*MULT + j;
  87.                 if(mx1[idx1] > mx1[idx2]) mx1[idx2] = mx1[idx1];
  88.             }
  89.         }
  90.         for(int j=n;j>=1;--j){
  91.             for(int i=j-1;i>=1;--i){
  92.                 int idx1 = (i+1)*MULT + j;
  93.                 int idx2 = i*MULT + j;
  94.                 if(mx2[idx1] > mx2[idx2]) mx2[idx2] = mx2[idx1];
  95.             }
  96.         }
  97.  
  98.         for(int i=1;i<=n;i++){
  99.             for(int j=i;j<=n;j++){
  100.                 int &mx = mx_block[i*MULT + j];
  101.                 if(!(prefMax[j] < i)) mx = k;
  102.                 int t1 = mx1[j*MULT + i];
  103.                 if(t1 > mx) mx = t1;
  104.                 int t2 = mx2[i*MULT + j];
  105.                 if(t2 > mx) mx = t2;
  106.                 int width = k - mx;
  107.                 if(width > 0){
  108.                     ll area = 1ll * (j - i + 1) * width;
  109.                     if(area > ans) ans = area;
  110.                 }
  111.             }
  112.         }
  113.  
  114.         for(int r=1;r<=n;r++) lastpos_set(a[r][k], r, k);
  115.         fill(prefMax.begin(), prefMax.end(), 0);
  116.     }
  117.  
  118.     cout << ans;
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GEVDX3
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!