ICPC2017 国内予選 C 池のある庭園

問題

日本語なので略
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1618&lang=jp

解法

与えられるデータの幅高さのうち大きいほうをnとすると、
nが小さいので、池の候補になりうる長方形をO(n^4)通り全探索して間に合う。
長方形をひとつ調べるのにO(n^2)かかるので全体の計算量はO(n^6).

ソースコード

int main(){
	int h, w;
	while(cin >> h >> w, h){
		vector<vi> in(h, vi(w));
		rep(i, h) rep(j, w) cin >> in[i][j];
		
		auto check = [&](int y, int x, int Y, int X){
			
			int omin = inf, imax = -1, isum = 0;
			for(int i = y; i <= Y; i++) for(int j = x; j <= X; j++){
				bool inner = (i != y && i != Y) && (j != x && j != X);
				if(inner){
					isum += in[i][j];
					imax = max(imax, in[i][j]);
				}
				else omin = min(omin, in[i][j]);
			}
			//dbg(omin, imax, isum);
			if(imax < 0 || omin <= imax) return -1;
			return omin * (Y - y - 1) * (X - x - 1) - isum;
		};
		int ans = 0;
		rep(Y, h) rep(y, Y) rep(X, w) rep(x, X) ans = max(ans, check(y, x, Y, X));
		cout << ans << endl;
	}
	return 0;
}