Submission #541403

#	Time	Username	Problem	Language	Result	Execution time	Memory
541403		nigus	Bomb (IZhO17_bomb)	C++14	46 / 100	1105 ms	79884 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef unsigned long long ull;

unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);

ll random2(){
    return (1ll << 31ll)*eng()+eng();
}

ll n,m,k,q,T;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const int MAXN = 2501;

bool grid[MAXN][MAXN] = {0};

bool covered[MAXN][MAXN] = {0};

int CS[MAXN][MAXN] = {0};

int sum(int i1, int j1, int i2, int j2){
    return CS[i2+1][j2+1] - CS[i1][j2+1] - CS[i2+1][j1] + CS[i1][j1];
}


bool can_place(int i, int j, int a, int b){

    if(n-i < a || m-j < b)return 0;
    return (sum(i,j,i+a-1,j+b-1) == 0);
    rep(c1,0,a){
        rep(c2,0,b){
            if(!grid[i+c1][j+c2])return 0;
        }
    }
    return 1;
}

bool can_cover(int i, int j, int a, int b){
    rep(dx,0,a){
        rep(dy,0,b){
            int i2 = i - dx;
            int j2 = j - dy;
            if(i2 >= 0 && j2 >= 0 && can_place(i2,j2,a,b))return 1;
        }
    }
    return 0;
}

bool solve(int a, int b){
    rep(c1,0,n){
        rep(c2,0,m){
            if(grid[c1][c2] && (c1 == n-1 || !grid[c1+1][c2] || c1 == 0 || !grid[c1-1][c2]) && !can_cover(c1,c2,a,b))return 0;
        }
    }
    return 1;
}

int lft[MAXN][MAXN] = {0};
int up[MAXN][MAXN] = {0};

int mina = big;
int minb = big;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

   // freopen("fhc.txt","r",stdin);
   // freopen("autput.txt","w",stdout);

    ll a,b,c,d,e;

    cin >> n >> m;
    rep(c1,0,n){
        string s;
        cin >> s;
        rep(c2,0,m){
            grid[c1][c2] = (s[c2] == '1');
        }
    }

    rep(c1,1,n+1){
        rep(c2,1,m+1){
            CS[c1][c2] = (!grid[c1-1][c2-1]) + CS[c1-1][c2] + CS[c1][c2-1] - CS[c1-1][c2-1];
        }
    }

    rep(c1,0,n){
        rep(c2,0,m){
            if(grid[c1][c2]){
                if(c1 == 0){
                    up[c1][c2] = 1;
                }
                else{
                    up[c1][c2] = up[c1-1][c2]+1;
                }

                if(c1 == n-1 || !grid[c1+1][c2])mina = min(mina, up[c1][c2]);

                if(c2 == 0){
                    lft[c1][c2] = 1;
                }
                else{
                    lft[c1][c2] = lft[c1][c2-1]+1;
                }

                if(c2 == m-1 || !grid[c1][c2+1])minb = min(minb, lft[c1][c2]);
            }
        }
    }

    ll ans = 0;

    rep(a,1,mina+1){

            int lo = 1;
            int hi = minb+1;
            while(lo < hi-1){
                int mid = (lo+hi)/2;
                if(solve(a, mid)){
                    lo = mid;
                }
                else{
                    hi = mid;
                }
            }
            ans = max(ans, ll(a)*ll(lo));

    }
    cout << ans << "\n";


    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:88:8: warning: unused variable 'a' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |        ^
bomb.cpp:88:10: warning: unused variable 'b' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |          ^
bomb.cpp:88:12: warning: unused variable 'c' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |            ^
bomb.cpp:88:14: warning: unused variable 'd' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |              ^
bomb.cpp:88:16: warning: unused variable 'e' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |                ^

• Subtask 1: 46 / 100