Submission #833808

#	Time	Username	Problem	Language	Result	Execution time	Memory
833808		vjudge1	Bomb (IZhO17_bomb)	C++17	19 / 100	1094 ms	32592 KiB

bomb

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 2505;

char inp[MX][MX];
int board[MX][MX];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    for(int i =1 ; i<= n ; i++)
    {
        for(int j =1 ; j <= m;j++)
        {
            cin >> inp[i][j];
            board[i][j] = inp[i][j] - '0';
            board[i][j] += board[i][j-1];
        }
    }
    for(int i =1 ; i<= n ; i++)
    {
        for(int j =1 ; j <= m;j++)
        {
            board[i][j] += board[i-1][j];
        }
    }
    // for(int i =1 ; i<= n ; i++)
    // {
    //     for(int j =1 ; j <= m;j++)
    //     {
    //         cout << board[i][j] <<" ";
    //     }
    //     cout << "\n";
    // }
    int ans = 0;
    for(int h = 1; h <= n; h++)
    {
        for(int w = 1; w <= m ; w++)
        {
            vector<vector<bool>> ok(MX, vector<bool>(MX,0));
            bool y = 1;
            for(int i =1 ; i<= n ; i++)
            {
                for(int j =1 ; j <= m;j++)
                {
                    if(inp[i][j] != '1'){
                        continue;
                    }
                    int sum = board[i+h-1][j+w-1];
                    sum -= board[i-1][j+w-1];
                    sum -= board[i+h-1][j-1];
                    sum += board[i-1][j-1];
                    if(sum != h*w)
                    {
                        if(ok[i][j]){
                            continue;
                        }
                        y = 0;
                        break;
                    }else{
                        for(int oi = i ; oi <= i+h-1; oi++){
                            for(int oj = j; oj <= j+w-1;oj++){
                                ok[oi][oj] = 1;
                            }
                        }
                    }
                }
                if(!y){
                    break;
                }
                
                
            }
            if(y){
                ans = max(ans, h*w);
            }
         }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 19 / 100