Submission #167193

#	Time	Username	Problem	Language	Result	Execution time	Memory
167193		hentai_lover	Bomb (IZhO17_bomb)	C++14	26 / 100	427 ms	3448 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define pb push_back
#define fr(i, l, r) for(ll i = l; i <= r; ++ i)
#define rf(i, l, r) for(ll i = l; i >= r; -- i)

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef int ll;
typedef pair<ll, ll> pll;

const ll oo = ll(1e9) + 10;

ll p[3000][300];

ll get(ll x1, ll y1, ll x2, ll y2){
    return p[x2][y2] - p[x2][y1 - 1] - p[x1 - 1][y2] + p[x1 - 1][y1 - 1];
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m, ansx = 0, ansy = 0, ans = 0;
    cin >> n >> m;
    if(n * m > 10000)return 0;
    char a[n + 1][m + 1];
    fr(i, 1, n)fr(j, 1, m){
        cin >> a[i][j];
        p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + 1 - (a[i][j] - '0');
    }
    rf(r, n, 1){
        rf(c, m, 1){
            vector <pll> v;
            fr(i, 1, n - r + 1){
                fr(j, 1, m - c + 1){
                    //if(a[i][j] == '0')continue;
                    //cout << "i = " << i << " j = " << j << " get = " << get(i, j, i + r - 1, j + c - 1) << endl;
                    if(get(i, j, i + r - 1, j + c - 1) == 0)v.pb({i, j});
                }
            }
            reverse(v.begin(), v.end());
            //cout << "r = " << r << " c = " << c << endl;
            //cout << "v: " << endl;
            //for(auto i : v)cout << i.first << ' ' << i.second << endl;
            bool usd[n + 1][m + 1];
            fr(i, 1, n)fr(j, 1, m)usd[i][j] = 0;
            for(auto x : v){
                fr(i, 0, r - 1){
                    if(usd[x.first + i][x.second])break;
                    fr(j, 0, c - 1){
                        if(usd[x.first + i][x.second + j])break;
                        usd[x.first + i][x.second + j] = 1;
                    }
                }
            }

            bool ok = 1;
            fr(i, 1, n){
                fr(j, 1, m){
                    if(a[i][j] == '1' && usd[i][j] == 0)ok = 0;
                }
            }
            if(ok)ans = max(ans, r * c);
        }
    }
    //cout << ansx << ' ' << ansy << endl;
    cout << ans;
}


/*
3 3
011
111
111
*/

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:31:14: warning: unused variable 'ansx' [-Wunused-variable]
     ll n, m, ansx = 0, ansy = 0, ans = 0;
              ^~~~
bomb.cpp:31:24: warning: unused variable 'ansy' [-Wunused-variable]
     ll n, m, ansx = 0, ansy = 0, ans = 0;
                        ^~~~

• Subtask 1: 26 / 100