1   2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #define M 2020 7 using namespace std; 8 int n,k,a[M][M]; 9 long long sum[M][M];10 long long Get_Sum(int x1,int y1,int x2,int y2)11 {12     return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];13 }14 void Output(int x1,int y1,int x2,int y2)15 {16     while( Get_Sum(x1,y1,x2,y2)>k*2 )17     {18         if(x1==x2)19             y2--;20         else21         {22             if( Get_Sum(x1+1,y1,x2,y2)>=k )23                 x1++;24             else25                 x2--;26         }27     }28     printf("%d %d %d %d\n",y1,x1,y2,x2);29     exit(0);30 }31 void Monotonous_Stack(int base,int h[])32 {33     static int stack[M],top;34     static int l[M],r[M];35     int i;36  37     for(top=0,i=1;i<=n+1;i++)38     {39         while( top && h[stack[top]]>h[i] )40             r[stack[top--]]=i-1;41         stack[++top]=i;42     }43     for(top=0,i=n;i>=0;i--)44     {45         while( top && h[stack[top]]>h[i] )46             l[stack[top--]]=i+1;47         stack[++top]=i;48     }49     for(i=1;i<=n;i++)50         if(h[i])51         {52             long long temp=Get_Sum(base-h[i]+1,l[i],base,r[i]);53             if( temp>=k )54                 Output(base-h[i]+1,l[i],base,r[i]);55         }56 }57 int main()58 {59     int i,j;60     cin>>k>>n;61     for(i=1;i<=n;i++)62         for(j=1;j<=n;j++)63         {64             scanf("%d",&a[i][j]);65             if( a[i][j]>=k && a[i][j]<=k*2 )66             {67                 printf("%d %d %d %d\n",j,i,j,i);68                 return 0;69             }70             sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];71         }72     static int h[M];73     for(i=1;i<=n;i++)74     {75         for(j=1;j<=n;j++)76             h[j]=a[i][j]>k*2?0:h[j]+1;77         Monotonous_Stack(i,h);78     }79     puts("NIE");80     return 0;81 }