玄学よ

時間:1000 ms/空間:131072 KiB/Javaクラス名:Main
説明
行列の重み値をこの行列の4つの角の数値の最小値として定義した.今、Mちゃんには行列があります.彼はこの行列の中で一番重みのあるサブ行列を探したいと思っています.この最大重みを教えてください.
入力フォーマット
第1行2個数n m
次のn*mのマトリクス
出力フォーマット
最大ウェイト値を表す1つの数
コメント
matrix.in
matrix.out
3 3 1 0 1 0 1 0 0 1 1
0
【様式解釈】
どのサブマトリクスの四角形を選択するも少なくとも1つは0であることがわかる.
 
10%のデータはn,m<=50を満たす
30%のデータはn,m<=200を満たす
100%のデータはnを満たし、m<=2000
すべての数値は10^9を超えません
n^2の作り方があるそうですが、二分ロゴを付けてもどうでもいいと思い、簡単そうに書いてみましたが、構想は実は一目でわかりました...

#include
#include
#include
#include
#include
#define inf 1e9
using namespace std;
int a[2005][2005];
bool flag[2005][2005];
int n,m;
 int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool pd(int mid)
{  for(int x=1;x<=n;x++)
      { for(int i=1;i<=m;i++)
       if(a[x][i]>=mid)
        { for(int j=i+1;j<=m;j++)
         {if(a[x][j]>=mid)
          {if(flag[i][j]==1) return 1;
          else flag[i][j]=1;
          }
         }
        }
      }
      return 0;
}
int main()
{cin>>n>>m;
	
	
		for(int i=1;i<=n;i++)
		{
		   for(int j=1;j<=m;j++)
		   { int x=read();
		   a[i][j]=x;
		   }
		}
	
	
	int l=0,r=inf;
	while(r-l>1)
	{
	 int mid=(l+r)>>1;
	    if(pd(mid)==true)
	     {l=mid;
	     }
	     else
	      r=mid;
	    memset(flag,0,sizeof(flag));  
	      
	}
	if(pd(r)==true) cout<