oj.uz

Submission #869709

# Submission time Handle Problem Language Result Execution time Memory
869709 2023-11-05T11:40:56 Z hentai_lover Bomb (IZhO17_bomb) C++14
11 / 100
 180 ms 3428 KB 
#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;


    ansx = oo, ansy = oo;

    fr(i, 1, n){
        fr(j, 1, m){
            if(a[i][j] == '0')continue;
            ll l = -1, r = -1, u = -1, d = -1;
            fr(x, i, n){
                if(a[x][j] == '0')break;
                r = x;
            }
            if(r < 0)r = n;
            rf(x, i, 1){
                if(a[x][j] == '0')break;
                l = x;
            }
            if(l < 0)l = 1;
            fr(x, j, m){
                if(a[i][x] == '0')break;
                d = x;
            }
            if(d < 0)d = m;
            rf(x, j, 1){
                //cout << "u = " << u << " i = " << i << " x = " << x << " a[i][x] = " << a[i][x] << endl;
                if(a[i][x] == '0')break;
                u = x;
            }
            if(u < 0)u = 1;


            ll a = r - l + 1;
            ll b = d - u + 1;
            //cout << "i = " << i << " j = " << j << "a = " << a << " b = " << b << " u = " << u << " d = " << d << endl;
            ansx = min(ansx, a);
            ansy = min(ansy, b);
        }
    }
    //cout << ansx << ' ' << ansy << endl;

    cout << ans;
    if(ans < ansx * ansy)cout<<1/0;
    ///cout << ansx * ansy << endl;
}


/*
3 3
011
111
111
*/

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:117:33: warning: division by zero [-Wdiv-by-zero]
  117 |     if(ans < ansx * ansy)cout<<1/0;
      |                                ~^~

Subtask #1
11.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 45 ms 3428 KB Output is correct
4 Correct 40 ms 3408 KB Output is correct
5 Correct 8 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 604 KB Execution killed with signal 4
9 Runtime error 1 ms 604 KB Execution killed with signal 4
10 Runtime error 1 ms 480 KB Execution killed with signal 4
11 Runtime error 1 ms 604 KB Execution killed with signal 4
12 Runtime error 1 ms 604 KB Execution killed with signal 4
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Runtime error 1 ms 604 KB Execution killed with signal 4
16 Correct 1 ms 348 KB Output is correct
17 Runtime error 19 ms 604 KB Execution killed with signal 4
18 Runtime error 15 ms 548 KB Execution killed with signal 4
19 Runtime error 40 ms 848 KB Execution killed with signal 4
20 Runtime error 44 ms 856 KB Execution killed with signal 4
21 Runtime error 19 ms 604 KB Execution killed with signal 4
22 Runtime error 41 ms 600 KB Execution killed with signal 4
23 Runtime error 83 ms 848 KB Execution killed with signal 4
24 Runtime error 27 ms 848 KB Execution killed with signal 4
25 Runtime error 80 ms 840 KB Execution killed with signal 4
26 Correct 180 ms 780 KB Output is correct
27 Incorrect 0 ms 344 KB Output isn't correct
28 Incorrect 0 ms 348 KB Output isn't correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Incorrect 0 ms 348 KB Output isn't correct
31 Incorrect 0 ms 348 KB Output isn't correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Incorrect 0 ms 348 KB Output isn't correct
34 Incorrect 0 ms 344 KB Output isn't correct
35 Incorrect 0 ms 348 KB Output isn't correct
36 Incorrect 0 ms 548 KB Output isn't correct
37 Runtime error 1 ms 604 KB Execution killed with signal 4
38 Incorrect 0 ms 348 KB Output isn't correct
39 Runtime error 1 ms 604 KB Execution killed with signal 4
40 Incorrect 0 ms 348 KB Output isn't correct
41 Runtime error 1 ms 604 KB Execution killed with signal 4
42 Runtime error 136 ms 856 KB Execution killed with signal 4
43 Incorrect 1 ms 348 KB Output isn't correct
44 Incorrect 1 ms 348 KB Output isn't correct
45 Incorrect 0 ms 348 KB Output isn't correct
46 Incorrect 0 ms 348 KB Output isn't correct
47 Incorrect 0 ms 348 KB Output isn't correct
48 Incorrect 1 ms 348 KB Output isn't correct
49 Incorrect 0 ms 348 KB Output isn't correct
50 Incorrect 0 ms 344 KB Output isn't correct
51 Incorrect 0 ms 348 KB Output isn't correct
52 Incorrect 1 ms 344 KB Output isn't correct
53 Incorrect 1 ms 348 KB Output isn't correct
54 Incorrect 0 ms 348 KB Output isn't correct
55 Incorrect 0 ms 348 KB Output isn't correct
56 Incorrect 0 ms 600 KB Output isn't correct
57 Incorrect 0 ms 348 KB Output isn't correct
58 Incorrect 0 ms 348 KB Output isn't correct
59 Incorrect 0 ms 344 KB Output isn't correct
60 Incorrect 0 ms 344 KB Output isn't correct
61 Incorrect 0 ms 348 KB Output isn't correct
62 Incorrect 0 ms 348 KB Output isn't correct
63 Incorrect 0 ms 348 KB Output isn't correct
64 Incorrect 0 ms 348 KB Output isn't correct
65 Incorrect 0 ms 348 KB Output isn't correct
66 Incorrect 1 ms 348 KB Output isn't correct
67 Incorrect 1 ms 348 KB Output isn't correct
68 Incorrect 0 ms 348 KB Output isn't correct
69 Incorrect 0 ms 348 KB Output isn't correct
70 Incorrect 0 ms 348 KB Output isn't correct
71 Incorrect 0 ms 348 KB Output isn't correct
72 Incorrect 0 ms 348 KB Output isn't correct
73 Incorrect 0 ms 348 KB Output isn't correct
74 Incorrect 0 ms 348 KB Output isn't correct
75 Incorrect 0 ms 348 KB Output isn't correct
76 Incorrect 1 ms 348 KB Output isn't correct
77 Incorrect 0 ms 360 KB Output isn't correct
78 Incorrect 0 ms 612 KB Output isn't correct
79 Incorrect 0 ms 360 KB Output isn't correct
80 Incorrect 0 ms 360 KB Output isn't correct
81 Incorrect 0 ms 360 KB Output isn't correct
82 Incorrect 0 ms 360 KB Output isn't correct
83 Incorrect 0 ms 360 KB Output isn't correct
84 Incorrect 0 ms 360 KB Output isn't correct
85 Incorrect 0 ms 360 KB Output isn't correct
86 Incorrect 0 ms 360 KB Output isn't correct
87 Incorrect 0 ms 360 KB Output isn't correct
88 Incorrect 0 ms 360 KB Output isn't correct
89 Incorrect 0 ms 360 KB Output isn't correct
90 Incorrect 0 ms 360 KB Output isn't correct
91 Incorrect 0 ms 360 KB Output isn't correct
92 Incorrect 0 ms 360 KB Output isn't correct
93 Incorrect 0 ms 360 KB Output isn't correct
94 Incorrect 0 ms 360 KB Output isn't correct
95 Incorrect 0 ms 360 KB Output isn't correct
96 Incorrect 0 ms 360 KB Output isn't correct
97 Incorrect 0 ms 360 KB Output isn't correct
98 Incorrect 0 ms 360 KB Output isn't correct
99 Incorrect 0 ms 360 KB Output isn't correct
100 Incorrect 0 ms 360 KB Output isn't correct