原来看过然后没做，结果板板把这道题改了改考掉了，血亏=。=
首先看看有没有符合条件的点。如果没有开始寻找解，先把所有的大于$2*k$的点设为坏点，然后求最大子矩形，只要一个最大子矩形的权值和超过$2*k$则它的一个子矩形一定可以成为解。因为这时所有点都小于$k$，这个最大子矩形既然权值和超过$2*k$那么一定是有一部分落在所求的区间中，然后逐行/列枚举切一下是一定有解的。
注意最大子矩形的边界(为什么你们的最大子矩形都要做两遍啊=。=)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct a
{
int xx,yy,zz;
}stk[N],str;
long long fsum[N][N];
int mapp[N][N],dp[N][N];
long long n,k,rd,top,ans;
void gun(){exit();}
long long getsum(int x1,int y1,int x2,int y2)
{
return fsum[x2][y2]-fsum[x1-][y2]-fsum[x2][y1-]+fsum[x1-][y1-];
}
void check(int x1,int y1,int x2,int y2)
{
if(x1>x2||y1>y2) return ;
long long sum=getsum(x1,y1,x2,y2); if(sum<k) return ;
if(sum>=k&&sum<=*k) printf("%d %d %d %d",y1,x1,y2,x2),gun();
for(int i=x1+;i<=x2;i++)
{
long long t1=getsum(i,y1,x2,y2),t2=sum-t1;
if(t1>=k&&t1<=*k) printf("%d %d %d %d",y1,i,y2,x2),gun();
else if(t2>=k&&t2<=*k) printf("%d %d %d %d",y1,x1,y2,i),gun();
}
return ;
}
int main ()
{
scanf("%lld%lld",&k,&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
scanf("%lld",&rd),mapp[i][j]=(rd<=*k),fsum[i][j]=rd;
if(rd<=*k&&rd>=k) printf("%d %d %d %d",j,i,j,i),gun();
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
fsum[i][j]+=fsum[i-][j]+fsum[i][j-]-fsum[i-][j-];
if(mapp[i][j]) dp[i][j]=dp[i-][j]+;
}
for(int i=;i<=n;i++)
for(int j=;j<=n+;j++)
{
str.xx=j,str.yy=dp[i][j],str.zz=i;
if(!top||stk[top].yy<str.yy) stk[++top]=str;
else
{
int tmp=j;
while(top&&stk[top].yy>=str.yy)
check(stk[top].zz-stk[top].yy+,stk[top].xx,stk[top].zz,j-),tmp=stk[top--].xx;
str.xx=tmp,stk[++top]=str;
}
}
printf("NIE");
return ;
}