MinhNGUYEN2k4

Untitled

Sep 20th, 2021
520
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, m, k;
  6. int a[5010][5010];
  7. int b[5010][5010];
  8.  
  9. int main(){
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(0);cout.tie(0);
  12.     cin >> n >> m >> k;
  13.     for(int i=1; i<=n; i++){
  14.         for(int j=1; j<=m; j++){
  15.             cin >> a[i][j];
  16.         }
  17.     }
  18.     for(int i=1; i<=n; i++){
  19.         deque<int> dq;
  20.         for(int j=1; j<=m; j++) {
  21.             while (dq.size() && a[i][dq.back()]<=a[i][j]) dq.pop_back();
  22.             dq.push_back(j);
  23.             while (dq.size() && j-dq.front()+1>k) dq.pop_front();
  24.             if (j>=k) b[i][j]=a[i][dq.front()];
  25.  
  26.         }
  27.     }
  28.     memset(a,0,sizeof a);
  29.     for(int i=k; i<=m; i++){
  30.         deque<int> dq;
  31.         for(int j=1; j<=n; j++){
  32.             while (dq.size() && b[dq.back()][i]<=b[j][i]) dq.pop_back();
  33.             dq.push_back(j);
  34.             while (dq.size() && j-dq.front()+1>k) dq.pop_front();
  35.             if (j>=k) a[j][i]=b[dq.front()][i];
  36.         }
  37.     }
  38.     long long ans=0;
  39.     for(int i=k; i<=n; i++){
  40.         for(int j=k; j<=m; j++){
  41.             ans += a[i][j];
  42.         }
  43.     }
  44.     cout << ans;
  45.     return 0;
  46. }
  47.  
RAW Paste Data