Submission #55452

#	Time	Username	Problem	Language	Result	Execution time	Memory
55452		BThero	Bomb (IZhO17_bomb)	C++17	42 / 100	1092 ms	132096 KiB

bomb

// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

int pref[2505][2505];

int arr[2505][2505];

char s[2505][2505];

int n, m, ans;

bool cmp(pair<int,int> a, pair<int,int> b) {
    return a.fi * a.se < b.fi * b.se;
}

int rectSum(int ax, int ay, int bx, int by) {
    int ret = pref[bx][by];

    ret -= pref[ax - 1][by];
    ret -= pref[bx][ay - 1];
    ret += pref[ax - 1][ay - 1];

    return ret;
}

void updRect(int ax, int ay, int bx, int by) {
    ++arr[bx][by];
    --arr[ax - 1][by];
    --arr[bx][ay - 1];
    ++arr[ax - 1][ay - 1];
}

bool check(int x, int y, bool dbg = 0) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            arr[i][j] = 0;
        }
    }

    for (int cx = x; cx <= n; ++cx) {
        for (int cy = y; cy <= m; ++cy) {
            if (rectSum(cx - x + 1, cy - y + 1, cx, cy) == x * y) {
                if (dbg) {
                    printf("NEW RECT: ");
                    printf("%d %d\n", cx, cy);
                }

                updRect(cx - x + 1, cy - y + 1, cx, cy);                
            }
        }
    }

    for (int i = n; i > 0; --i) {
        for (int j = m; j > 0; --j) {
            arr[i][j] -= arr[i + 1][j + 1];
            arr[i][j] += arr[i + 1][j];
            arr[i][j] += arr[i][j + 1];
        }
    }
    
    bool good = 1;

    if (dbg) {
        printf("----------------------\n");

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                printf("%d ", arr[i][j]);
            }

            printf("\n");
        }

        printf("----------------------\n");
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i][j] == '1' && arr[i][j] == 0) {
                good = 0;
            }
        }
    }

    return good;
}

void solve() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        scanf("%s", s[i] + 1);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            pref[i][j] = (s[i][j] - '0');
            pref[i][j] += pref[i - 1][j];
            pref[i][j] += pref[i][j - 1];
            pref[i][j] -= pref[i - 1][j - 1];
        }
    }

    int limx = n, limy = m;

    for (int i = 1; i <= n; ++i) {
        for (int l = 1, r; l <= m; l = r) {
            r = l + 1;

            if (s[i][l] == '0') {
                continue;
            }

            while (s[i][l] == s[i][r]) {
                ++r;
            }

            limy = min(limy, r - l);            
        }
    }

    for (int i = 1; i <= m; ++i) {
        for (int l = 1, r; l <= n; l = r) {
            r = l + 1;

            if (s[l][i] == '0') {
                continue;
            }

            while (s[l][i] == s[r][i]) {
                ++r;
            }

            limx = min(limx, r - l);
        }    
    }                     
    
    for (int cx = limx, cy = 0; cx > 0; --cx) {
        while (cy < limy && check(cx, cy + 1)) {
            ++cy;
        }    

        ans = max(ans, cx * cy);
    }

    printf("%d\n", ans);
}

int main() {
    //freopen("bomb.in", "r", stdin);
    //freopen("bomb.out", "w", stdout);
          
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'void solve()':
bomb.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
bomb.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s[i] + 1);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 42 / 100