fork download 
  1. /*
  2.     Cred : SunnyYeahBoi
  3.     It's my last chance (⌐■_■)
  4.     Problem :
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12. #define double long double
  13. #define endl "\n"
  14. #define NAME "a"
  15.  
  16. const int MAXN = 1e3 + 5;
  17. const int inf = 1e18;
  18. const int MOD = 1e9 + 7;
  19.  
  20. void FileInput(){
  21.     if(fopen(NAME".inp" , "r") == NULL)
  22.         freopen(NAME".inp" , "w" , stdout);
  23.     freopen(NAME".inp" , "r" , stdin);
  24.     freopen(NAME".out" , "w" , stdout);
  25. }
  26.  
  27. int m , n , k;
  28. int a[MAXN][MAXN];
  29. int b[MAXN];
  30. deque<int> q[MAXN];
  31. int result = -inf;
  32.  
  33. void calc(){
  34.     for(int i = 1 ; i <= n ; i++)
  35.         b[i] = a[q[i].front()][i];
  36.  
  37.     deque<int> dq;
  38.  
  39.     for(int i = 1 ; i <= n ; i++){
  40.         while(!dq.empty() && b[dq.back()] >= b[i])
  41.             dq.pop_back();
  42.         dq.push_back(i);
  43.         if(dq.front() < i - k + 1) dq.pop_front();
  44.  
  45.         if(i >= k)result = max(result , b[dq.front()]);
  46.     }
  47. }
  48.  
  49. void solve(){
  50.     cin >> m >> n >> k;
  51.     for(int i = 1 ; i <= m ; i++)
  52.         for(int j = 1 ; j <= n ; j++)
  53.             cin >> a[i][j];
  54.  
  55.     for(int j = 1 ; j <= n ; j++){
  56.         for(int i = 1 ; i <= k - 1 ; i++){
  57.             while(!q[j].empty() && a[q[j].back()][j] >= a[i][j]) 
  58.                 q[j].pop_back();
  59.             q[j].push_back(i);
  60.         }
  61.     }
  62.  
  63.     for(int i = k ; i <= m ; i++){
  64.         for(int j = 1 ; j <= n ; j++){
  65.             while(!q[j].empty() && a[q[j].back()][j] >= a[i][j]) 
  66.                 q[j].pop_back();
  67.             q[j].push_back(i);
  68.             if(q[j].front() < i - k + 1) q[j].pop_front();
  69.  
  70.         }
  71.         calc();
  72.     }
  73.  
  74.     cout << result << endl;
  75. }
  76.  
  77. int32_t main(){
  78.     //FileInput();
  79.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  80.     int t = 1;
  81.     // cin >> t;
  82.     while(t--)
  83.         solve();
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
-1000000000000000000
https://ideone.com/13VwCu
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!