Cod sursa(job #2409981)

Utilizator flibiaVisanu Cristian flibia Data 19 aprilie 2019 16:53:55
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("bmatrix.in");
ofstream out("bmatrix.out");

int n, m, a[210][210], s[210][210], dpo[210][210], dpv[210][210];
char c;

int main() {
	in >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			in >> c, a[i][j] = (c - '0' ? -4e4 : 1);
			
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
	
	for (int i = 1; i <= n; i++)
		for (int j = i; j > 0; j--) {
			int mn = 0;
			for (int k = 1; k <= m; k++) {
				dpv[j][i] = max(dpv[j][i], s[i][k] - s[j - 1][k] - mn);
				mn = min(mn, s[i][k] - s[j - 1][k]);
			}
			if (i != j)
				dpv[j][i] = max({dpv[j][i], dpv[j + 1][i], dpv[j][i - 1]});
		}
		
	for (int i = 1; i <= m; i++)
		for (int j = i; j > 0; j--) {
			int mn = 0;
			for (int k = 1; k <= n; k++) {
				dpo[j][i] = max(dpo[j][i], s[k][i] - s[k][j - 1] - mn);
				mn = min(mn, s[k][i] - s[k][j - 1]);
			}
			if (i != j)
				dpo[j][i] = max({dpo[j][i], dpo[j + 1][i], dpo[j][i - 1]});
		} 		
		
	int rs = 0;
	for (int i = 1; i < n; i++)
		rs = max(rs, dpv[1][i] + dpv[i + 1][n]);
	for (int i = 1; i < m; i++)
		rs = max(rs, dpo[1][i] + dpo[i + 1][m]);
		
	out << rs;
	return 0;
}