1 条题解

  • 0
    @ 2023-2-18 11:07:37
    #include<bits/stdc++.h>
    using namespace std;
    const int M = 1100;
    int n, m, ans = 0;
    int c;
    int mp[M][M];
    int l[M][M], r[M][M], up[M][M];
    int b[M][M];
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(0), cout.tie(0);
    	cin >> n >> m;
    	for(int i = 1; i <= n; i ++)
    		for(int j = 1; j <= m; j ++) {
    			cin >> c;
    			b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + c;
    			if(c) mp[i][j] = 1;
    			l[i][j] = r[i][j] = j;
    			up[i][j] = 1;
    		}
    	for(int i = 1; i <= n; i ++)
    		for(int j = 1; j <= m; j ++)
    			if(mp[i][j] && mp[i][j - 1])
    				l[i][j] = l[i][j - 1];
    	for(int i = 1; i <= n; i ++)
    		for(int j = m; j >= 1; j --)
    			if(mp[i][j] && mp[i][j + 1])
    				r[i][j] = r[i][j + 1];
    	for(int i = 1; i <= n; i ++)
    		for(int j = 1; j <= m; j ++) {
    			if(mp[i][j] && mp[i - 1][j]) {
    				up[i][j] = up[i - 1][j] + 1;
    				r[i][j] = min(r[i][j], r[i - 1][j]);
    				l[i][j] = max(l[i][j], l[i - 1][j]);
    			}
    			int x = i, y = r[i][j];
    			int x1 = i - up[i][j], y1 = l[i][j] - 1;
    			ans = max(ans, b[x][y] - b[x][y1] - b[x1][y] + b[x1][y1]);
    		}
    	cout << ans;
    	return 0;
    }
    
    • 1

    信息

    ID
    295
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    112
    已通过
    10
    上传者