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