20pts #145 AC三个TLE其他WA求条,悬3关

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,n;
int g[2005][2005];
deque<int>dq1,dq2;
inline void add1(int x){
     while(!dq1.empty()&&dq1.back()<x)
         dq1.pop_back();
    dq1.push_back(x);
}
inline void del1(int x){
    if(dq1.front()==x) dq1.pop_front();
}
inline void add2(int x){
     while(!dq2.empty()&&dq2.back()>x)
         dq2.pop_back();
    dq2.push_back(x);
}
inline void del2(int x){
    if(dq2.front()==x) dq2.pop_front();
}
signed main(){
    cin>>a>>b>>n;
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            cin>>g[i][j];
        }
    }
    int ans=1e18;
    for(int i=1;i<=a;i++){
        dq1.clear();
        dq2.clear();
        for(int j=i;j<=i+n-1;j++){
            for(int k=1;k<=n;k++){
                add1(g[j][k]);
                add2(g[j][k]);
            }
        }
        for(int j=1;j<=b;j++){
            ans=min(ans,dq1.front()-dq2.front());
            if(j>n){
                for(int k=i;k<=i+n-1;k++){
                    del1(g[k][j]);
                    del2(g[k][j]);
                }
            }
            for(int k=i;k<=i+n-1;k++){
                add1(g[k][j+n-1]);
                add2(g[k][j+n-1]);
            }
        }
    }
    cout<<ans;
}