fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("O3")
  4. #pragma GCC optimize("O1")
  5. #pragma GCC optimize("O1")
  6. #pragma GCC optimize("unroll-loops")
  7. #pragma GCC optimize(3)
  8. #pragma GCC optimize("Ofast")
  9. #pragma GCC optimize("inline")
  10. #pragma GCC optimize("-fgcse")
  11. #pragma GCC optimize("-fgcse-lm")
  12. #pragma GCC optimize("-fipa-sra")
  13. #pragma GCC optimize("-ftree-pre")
  14. #pragma GCC optimize("-ftree-vrp")
  15. #pragma GCC optimize("-fpeephole2")
  16. #pragma GCC optimize("-ffast-math")
  17. #pragma GCC optimize("-fsched-spec")
  18. #pragma GCC optimize("-falign-jumps")
  19. #pragma GCC optimize("-falign-loops")
  20. #pragma GCC optimize("-falign-labels")
  21. #pragma GCC optimize("-fdevirtualize")
  22. #pragma GCC optimize("-fcaller-saves")
  23. #pragma GCC optimize("-fcrossjumping")
  24. #pragma GCC optimize("-fthread-jumps")
  25. #pragma GCC optimize("-freorder-blocks")
  26. #pragma GCC optimize("-fschedule-insns")
  27. #pragma GCC optimize("inline-functions")
  28. #pragma GCC optimize("-ftree-tail-merge")
  29. #pragma GCC optimize("-fschedule-insns2")
  30. #pragma GCC optimize("-fstrict-aliasing")
  31. #pragma GCC optimize("-falign-functions")
  32. #pragma GCC optimize("-fcse-follow-jumps")
  33. #pragma GCC optimize("-fsched-interblock")
  34. #pragma GCC optimize("-fpartial-inlining")
  35. #pragma GCC optimize("no-stack-protector")
  36. #pragma GCC optimize("-freorder-functions")
  37. #pragma GCC optimize("-findirect-inlining")
  38. #pragma GCC optimize("-fhoist-adjacent-loads")
  39. #pragma GCC optimize("-frerun-cse-after-loop")
  40. #pragma GCC optimize("inline-small-functions")
  41. #pragma GCC optimize("-finline-small-functions")
  42. #pragma GCC optimize("-ftree-switch-conversion")
  43. #pragma GCC optimize("-foptimize-sibling-calls")
  44. #pragma GCC optimize("-fexpensive-optimizations")
  45. #pragma GCC optimize("inline-functions-called-once")
  46. #pragma GCC optimize("-fdelete-null-pointer-checks")
  47.  
  48. #define int long long
  49. #define cint const int
  50. #define ii pair<int, int>
  51. #define fi first
  52. #define se second
  53. #define vi vector<int>
  54. #define vii vector<vi>
  55. #define pb push_back
  56. #define eb emplace_back
  57. #define pq priority_queue
  58. #define mid(l, r) ((l + r) >> 1)
  59. #define left(id) (id << 1)
  60. #define right(id) ((id << 1) | 1)
  61. #define cntbit(mask) __builtin_popcountll(mask)
  62. #define BIT(mask, i) (mask & (1ll << (i)))
  63. #define ONBIT(mask, i) (mask | (1ll << (i)))
  64.  
  65. const int MAXN = 1e5 + 15;
  66. const int oo   = 1e18;
  67. const int MOD  = 1e9 + 7;
  68. const int NMAX = 70;
  69.  
  70. int M, N, K;
  71. int A[NMAX][NMAX], B[NMAX][NMAX];
  72.  
  73. int calc(const vector<vector<bool>>& mat) {
  74.     if (mat.empty()) return 0;
  75.     int m = (int)mat.size();
  76.     int n = (int)mat[0].size();
  77.  
  78.     vector<int> f(n, 0), st;
  79.     vector<int> g(n, 0);
  80.     st.reserve(n);
  81.  
  82.     int ret = 0;
  83.  
  84.     for (int i = 0; i < m; i++) {
  85.         for (int j = 0; j < n; j++) {
  86.             if (mat[i][j]) f[j]++;
  87.             else f[j] = 0;
  88.  
  89.             while (!st.empty() && f[st.back()] >= f[j]) st.pop_back();
  90.             g[j] = st.empty() ? -1 : st.back();
  91.             st.push_back(j);
  92.         }
  93.  
  94.         st.clear();
  95.  
  96.         for (int j = n - 1; j >= 0; j--) {
  97.             while (!st.empty() && f[st.back()] >= f[j]) st.pop_back();
  98.             int t = st.empty() ? n : st.back();
  99.             ret = max(ret, f[j] * (t - g[j] - 1));
  100.             st.push_back(j);
  101.         }
  102.  
  103.         st.clear();
  104.     }
  105.  
  106.     return ret;
  107. }
  108.  
  109. void PROCESS() {
  110.     if (!(cin >> M >> N >> K)) return;
  111.  
  112.     for (int i = 1; i <= M; i++)
  113.         for (int j = 1; j <= N; j++)
  114.             cin >> A[i][j];
  115.  
  116.     for (int i = 1; i <= M; i++)
  117.         for (int j = 1; j <= N; j++)
  118.             cin >> B[i][j];
  119.  
  120.     int ans = 0;
  121.  
  122.     for (int i = 1; i < M + M; i++) {
  123.         for (int j = 1; j < N + N; j++) {
  124.  
  125.             int Ax1 = max(i - M + 1, 1ll), Ay1 = max(j - N + 1, 1ll);
  126.             int Ax2 = min(i, M), Ay2 = min(j, N);
  127.  
  128.             int Bx1 = Ax1 + M - i;
  129.             int By1 = Ay1 + N - j;
  130.  
  131.             int ms = Ax2 - Ax1 + 1;
  132.             int ns = Ay2 - Ay1 + 1;
  133.             if (ms <= 0 || ns <= 0) continue;
  134.  
  135.             vector<vector<bool>> v(ms, vector<bool>(ns, false));
  136.  
  137.             for (int x = 0; x < ms; x++) {
  138.                 for (int y = 0; y < ns; y++) {
  139.                     long long va = (long long)A[Ax1 + x][Ay1 + y];
  140.                     long long vb = (long long)B[Bx1 + x][By1 + y];
  141.                     v[x][y] = (llabs(va - vb) <= (long long)K);
  142.                 }
  143.             }
  144.  
  145.             ans = max(ans, calc(v));
  146.         }
  147.     }
  148.  
  149.     cout << ans << '\n';
  150. }
  151.  
  152.  
  153. signed main() {
  154.     ios_base::sync_with_stdio(0);
  155.     cin.tie(0);
  156.     cout.tie(0);
  157.  
  158.     PROCESS();
  159.     return 0;
  160. }
  161.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SxbWDI
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!