Skip to content

Instantly share code, notes, and snippets.

@odanado
Created July 15, 2017 01:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save odanado/abeb3a647da9bc14110295068d267472 to your computer and use it in GitHub Desktop.
Save odanado/abeb3a647da9bc14110295068d267472 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(n);i++)
#define out(S) cout<<(S)<<endl;
int H, W;
int area[11][11];
int min_out(int y, int x, int h, int w) {
int ret = 1000;
rep(i, H) rep(j, W) {
if (y <= i && i <= y + h - 1 && x <= j && j <= x + w - 1) {
if (i == y) ret = min(ret, area[i][j]);
if (j == x) ret = min(ret, area[i][j]);
if (i == y + h - 1) ret = min(ret, area[i][j]);
if (j == x + w - 1) ret = min(ret, area[i][j]);
}
}
return ret;
}
int max_in(int y, int x, int h, int w) {
int ret = 0;
rep(i, H) rep(j, W) {
if (y < i && i < y + h - 1 && x < j && j < x + w - 1) {
// cout << "in = " << i << ", " << j << endl;
ret = max(ret, area[i][j]);
}
}
return ret;
}
int sum_in(int y, int x, int h, int w) {
int ret = 0;
rep(i, H) rep(j, W) {
if (y < i && i < y + h - 1 && x < j && j < x + w - 1) {
// cout << "in = " << i << ", " << j << endl;
ret += area[i][j];
}
}
return ret;
}
void solve() {
// cout << min_out(0, 1, 3, 5) << endl;
// cout << max_in(0, 1, 3, 5) << endl;
int ans = 0;
rep(y, H) rep(x, W) rep(h, H + 1) rep(w, W + 1) {
if (h < 3) continue;
if (w < 3) continue;
if (y + h - 1 >= H) continue;
if (x + w - 1 >= W) continue;
int a = min_out(y, x, h, w);
int b = max_in(y, x, h, w);
if (b >= a) continue;
int s = sum_in(y, x, h, w);
int c = a * (h - 2) * (w - 2);
// printf("%d %d %d %d = %d %d %d %d: %d\n", y, x, h, w, a, b, s, c, c - s);
ans = max(ans, c - s);
}
cout << ans << endl;
}
int main() {
while (cin >> H >> W, H) {
rep(i, H) rep(j, W) cin >> area[i][j];
solve();
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment