fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int INF = -1e9;
  6.  
  7. int main() {
  8.     ios::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.  
  11.     int n, m, k;
  12.     cin >> n >> m >> k;
  13.     vector<vector<int>> a(n+1, vector<int>(m+1));
  14.     vector<vector<bool>> b(n+1, vector<bool>(m+1));
  15.     vector<vector<bool>> b1(n+1, vector<bool>(m+1));
  16.  
  17.     for (int i = 1; i <= n; i++)
  18.         for (int j = 1; j <= m; j++)
  19.             cin >> a[i][j];
  20.  
  21.     int len = 2 * k + 1;
  22.     vector<vector<int>> pref(n + 1, vector<int>(m + 1, 0));
  23.     for (int i = 1; i <= n; i++) {
  24.         for (int j = 1; j <= m; j++) {
  25.             pref[i][j] = a[i][j]+ pref[i - 1][j]+ pref[i][j - 1]- pref[i - 1][j - 1];
  26.         }
  27.     }
  28.     vector<vector<int>> rowMax(n+1, vector<int>(m+1));
  29.     vector<int> c(260);
  30.     for (int i = 1; i <= n; i++) {
  31.         deque<int> dq;
  32.         for (int j = 1; j <= m; j++) {
  33.             c[a[i][j]]++;
  34.             while (!dq.empty() && a[i][dq.back()] <= a[i][j]) dq.pop_back();
  35.             dq.push_back(j);
  36.             if (dq.front() <= j - len) dq.pop_front();
  37.             if(j-len >= 1){
  38.                 c[a[i][ j-len]]--;
  39.             }
  40.             if(j-len >=0){
  41.                 int x = a[i][dq.front()];
  42.                 rowMax[i][j-k] = x;
  43.                 if(c[x]==1)b[i][j-k] = true; 
  44.                 // cout << x<< " ";
  45.             }
  46.         }
  47.         for(int j = m; j>m-len;j--)c[a[i][j]]=0;
  48.         // cout << "\n";
  49.     }
  50.     vector<vector<int>> maxInSquare(n+1, vector<int>(m+1));
  51.     // vector<int> c(260);
  52.     for (int j = k+1; j +k<= m; j++) {
  53.         deque<int> dq;
  54.         for (int i = 1; i <= n; i++) {
  55.             c[rowMax[i][j]]+=2-b[i][j];
  56.             while (!dq.empty() && rowMax[dq.back()][j] <= rowMax[i][j]) dq.pop_back();
  57.             dq.push_back(i);
  58.             if (dq.front() <= i - len) dq.pop_front();
  59.             if(i-len>=1)c[rowMax[i-len][j]]-=2-b[i-len][j];
  60.             if(i-len >= 0){
  61.                 int x = rowMax[dq.front()][j];
  62.                 maxInSquare[i-k][j] = x;
  63.                 if(c[x]==1)b1[i-k][j] = true;
  64.                 // cout << x << ":" <<c[x] << " ";
  65.  
  66.             }
  67.         }
  68.         for (int i = n; i > n-len; i--) {
  69.             c[rowMax[i][j]]=0;
  70.         }
  71.         // cout << "\n";
  72.     }
  73.  
  74.     long long ans = 0;
  75.     bool found = false;
  76.  
  77.     for (int i = k+1; i + k <= n; i++) {
  78.         for (int j = k+1; j + k <= m; j++) {
  79.             int maxVal = maxInSquare[i][j];
  80.             // cout << maxVal <<  ":" << a[i][j] << " ";
  81.             if (a[i][j] == maxVal && b1[i][j]) {
  82.                 int x1 = i - k-1, y1 = j - k-1;
  83.                 int x2 = i + k, y2 = j + k ;
  84.                 long long sum = pref[x2][y2]-pref[x1][y2]-pref[x2][y1] + pref[x1][y1];
  85.                 // cout << sum << " ";
  86.                 ans = max(ans, sum);
  87.                 found = true;
  88.             }
  89.         }
  90.         // cout << "\n";
  91.     }
  92.  
  93.     cout << (found ? ans : 0) << "\n";
  94.  
  95.     return 0;
  96. }
  97.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/vj3QvZ
language:
C++ (gcc 8.3)
created:
11 hours 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!