1 #include<bits/stdc++.h>  2 using namespace std;  3 #define A 1005  4 #define N 105  5 int an=1000000001,h2,t2,h1,t1,a,b,n;  6 int pos1[A],pos2[A],que1[A],que2[A];  7 int mip1[A][A],map1[A][A];  8 int mip2[A][A],map2[A][A];  9 int read(){  //  读入优化  10     int ans=0; 11     char ch=getchar(); 12     for(;!isdigit(ch);ch=getchar()); 13     for(;isdigit(ch);ch=getchar()) 14         ans=ans*10+ch-‘0‘; 15     return ans; 16 } 17 int main(){ 18     a=read(),b=read(),n=read(); 19     for(int k,i=1;i<=a;i++){ 20         h1=h2=1; 21         t1=t2=0; 22         for(int j=1;j<=b;j++){ 23             k=read(); 24              25             for(;t1>=h1&&k>=que1[t1];t1--); 26             que1[++t1]=k; 27             pos1[t1]=j; 28              29             for(;t2>=h2&&k<=que2[t2];t2--); 30             que2[++t2]=k; 31             pos2[t2]=j; 32              33             if(j>=n){ 34                 map1[i][j]=que1[h1]; 35                 mip1[i][j]=que2[h2]; 36                 if(pos1[h1]==j-n+1)h1++; 37                 if(pos2[h2]==j-n+1)h2++; 38             } 39         } 40     } 41     /*cout<<endl; 42     for(int i=1;i<=a;i++){ 43       for(int j=1;j<=b;j++) 44         cout<<map1[i][j]<<" "; 45       cout<<endl; 46     } 47     cout<<endl; 48     for(int i=1;i<=a;i++){ 49       for(int j=1;j<=b;j++) 50         cout<<mip1[i][j]<<" "; 51       cout<<endl; 52     } 53     cout<<endl;*/ 54     for(int k1,k2,i=n;i<=b;i++){ 55         h1=h2=1; 56         t1=t2=0; 57         for(int j=1;j<=a;j++){ 58             k1=map1[j][i]; 59             k2=mip1[j][i]; 60              61             for(;t1>=h1&&k1>=que1[t1];t1--); 62             que1[++t1]=k1; 63             pos1[t1]=j; 64              65             for(;t2>=h2&&k2<=que2[t2];t2--); 66             que2[++t2]=k2; 67             pos2[t2]=j; 68              69              70             if(j>=n){ 71               //map2[j][i]=que1[h1]; 72               //mip2[j][i]=que2[h2]; 73               an=min(an,que1[h1]-que2[h2]); 74               if(pos1[h1]==j-n+1)h1++; 75               if(pos2[h2]==j-n+1)h2++; 76             } 77         } 78     } 79      80     /*for(int i=1;i<=a;i++){ 81       for(int j=1;j<=b;j++) 82         cout<<map2[i][j]<<" "; 83       cout<<endl; 84     } 85     cout<<endl; 86     for(int i=1;i<=a;i++){ 87       for(int j=1;j<=b;j++) 88         cout<<mip2[i][j]<<" "; 89       cout<<endl; 90     } 91     cout<<endl;*/ 92      93     cout<<an; 94      95     return 0; 96 }/*5 4 2  97 1 2 5 6  98 0 17 16 0  99 16 17 0 1 100 2 10 2 1 101 1 2 3 2102 103 2104 */