제출 #915562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915562		SeDunion	Bomb (IZhO17_bomb)	C++17	40 / 100	1105 ms	104888 KiB

bomb

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
 
#define int long long 
#define pb push_back
#define ui unsigned int
#define ld long double
#define pl pair<long long int,  long long int>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first    
#define ss second
#define sz size()
#define all(x) x.begin(), x.end()
 
using namespace std;
 
const int maxn = 1e6 + 11;
const int inf = 1e17 + 1;
const int mod = 1e9 + 7;
// const int mod = 998244353;
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1 , 0, -1, 1, -1, 1};
const double eps = 1e-10;

int n, m;

int pr[2505][2505], p[2505][2505];

void solve() {
    cin >> n >> m;

    char ch[n + 5][m + 5];
    int cnt = 0;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> ch[ i ][ j ];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            pr[ i ][ j ] = pr[i - 1][ j ] + pr[ i ][j - 1] - pr[i - 1][j - 1] + (ch[ i ][ j ] - '0');
        }
    }
    int y = m;
    int x = 1;
    int ans = 0;

    while(x <= n && y) {
        int l = 1, r = y;
        int anss = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            for(int i = 0; i <= n; i++) {
                for(int j = 0; j <= m; j++) {
                    p[ i ][ j ] = 0;
                }
            }
            for(int i = 0; i + x <= n; i++) {
                for(int j = 0; j + mid <= m; j++) {
                    int c = pr[i + x][j + mid] - pr[i + x][ j ] - pr[ i ][j + mid] + pr[ i ][ j ];

                    if(c == x * mid) {
                        p[i + x + 1][j + mid + 1]++;
                        p[i + 1][j + mid + 1]--;
                        p[i + x + 1][j + 1]--;
                        p[i + 1][j + 1]++;
                    }
                }
            }

            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    p[ i ][ j ] += p[i - 1][ j ] + p[ i ][j - 1] - p[i - 1][j - 1];
                }
            }
            bool fl = true;
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    if(ch[ i ][ j ] == '1' && p[ i ][ j ] == 0) {
                        fl = false;
                        break;
                    }
                }
            }
            if(fl) {
                anss = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        y = anss;
        ans = max(ans, x * y);
        x++;
    }
    cout << ans;
}
    
signed main() {
    // freopen("sum.in", "r", stdin); 
    // freopen("sum.out", "w", stdout);
 
    boost;      

    int tt = 1;

    // cin >> tt;

    for(int i = 1; i <= tt; i++) {
        // cout << "Case " << i << ":\n";
        solve();    
    }           
}

컴파일 시 표준 에러 (stderr) 메시지

bomb.cpp: In function 'void solve()':
bomb.cpp:55:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |             int mid = l + r >> 1;
      |                       ~~^~~
bomb.cpp:35:9: warning: unused variable 'cnt' [-Wunused-variable]
   35 |     int cnt = 0;
      |         ^~~

• Subtask 1: 40 / 100