fork download
copy 
  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.     vector<int> c(260);
  29.     for (int i = 1; i <= n; i++) {
  30.         deque<int> dq;
  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.         for(int j = m; j>m-len;j--)c[a[i][j]]=0;
  47.         // cout << "\n";
  48.     }
  49.     vector<vector<int>> maxInSquare(n+1, vector<int>(m+1));
  50.     // vector<int> c(260);
  51.     for (int j = k+1; j +k<= m; j++) {
  52.         deque<int> dq;
  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.         for (int i = n; i > n-len; i--) {
  68.             c[rowMax[i][j]]=0;
  69.         }
  70.         // cout << "\n";
  71.     }
  72.  
  73.     // // =====================
  74.     // // 3. Duyệt tìm vùng sáng nổi bật nhất
  75.     // // =====================
  76.     long long ans = 0;
  77.     bool found = false;
  78.  
  79.     for (int i = k+1; i + k <= n; i++) {
  80.         for (int j = k+1; j + k <= m; j++) {
  81.             int maxVal = maxInSquare[i][j];
  82.             // cout << maxVal <<  ":" << a[i][j] << " ";
  83.             if (a[i][j] == maxVal && b1[i][j]) {
  84.                 int x1 = i - k-1, y1 = j - k-1;
  85.                 int x2 = i + k, y2 = j + k ;
  86.                 long long sum = pref[x2][y2]-pref[x1][y2]-pref[x2][y1] + pref[x1][y1];
  87.                 // cout << sum << " ";
  88.                 ans = max(ans, sum);
  89.                 found = true;
  90.             }
  91.         }
  92.         // cout << "\n";
  93.     }
  94.  
  95.     cout << (found ? ans : 0) << "\n";
  96.  
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WSsfRf
language:
C++ (gcc 8.3)
created:
8 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!