oj.uz

Submission #541396

# Submission time Handle Problem Language Result Execution time Memory
541396 2022-03-23T13:11:07 Z nigus Bomb (IZhO17_bomb) C++14
29 / 100
 1000 ms 8424 KB 
#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 = 1001;

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

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

bool can_place(int i, int j, int a, int b){
    if(n-i < a || m-j < b)return 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] && !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,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){
        rep(b,1,minb+1){
            if(solve(a, b)){
                ans = max(ans, (ll)a*b);
            }
        }
    }
    cout << ans << "\n";


    return 0;
}

Compilation message

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

Subtask #1
29.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Runtime error 2 ms 2384 KB Execution killed with signal 11
4 Runtime error 2 ms 2388 KB Execution killed with signal 11
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 456 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 75 ms 868 KB Output is correct
20 Correct 85 ms 876 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 676 ms 964 KB Output is correct
24 Correct 74 ms 852 KB Output is correct
25 Execution timed out 1084 ms 1108 KB Time limit exceeded
26 Correct 72 ms 1236 KB Output is correct
27 Correct 4 ms 2904 KB Output is correct
28 Correct 6 ms 1108 KB Output is correct
29 Execution timed out 1065 ms 3800 KB Time limit exceeded
30 Execution timed out 1084 ms 3284 KB Time limit exceeded
31 Execution timed out 1088 ms 2388 KB Time limit exceeded
32 Execution timed out 1080 ms 3412 KB Time limit exceeded
33 Execution timed out 1086 ms 4180 KB Time limit exceeded
34 Correct 11 ms 1236 KB Output is correct
35 Execution timed out 1082 ms 1376 KB Time limit exceeded
36 Execution timed out 1082 ms 4436 KB Time limit exceeded
37 Correct 1 ms 468 KB Output is correct
38 Runtime error 7 ms 2880 KB Execution killed with signal 11
39 Correct 1 ms 468 KB Output is correct
40 Execution timed out 1069 ms 8424 KB Time limit exceeded
41 Correct 2 ms 468 KB Output is correct
42 Execution timed out 1089 ms 1108 KB Time limit exceeded
43 Runtime error 7 ms 2900 KB Execution killed with signal 11
44 Execution timed out 1080 ms 4436 KB Time limit exceeded
45 Runtime error 7 ms 2936 KB Execution killed with signal 11
46 Runtime error 7 ms 2904 KB Execution killed with signal 11
47 Runtime error 7 ms 2932 KB Execution killed with signal 11
48 Runtime error 7 ms 2888 KB Execution killed with signal 11
49 Runtime error 6 ms 2960 KB Execution killed with signal 11
50 Runtime error 6 ms 2900 KB Execution killed with signal 11
51 Runtime error 7 ms 3000 KB Execution killed with signal 11
52 Runtime error 6 ms 2900 KB Execution killed with signal 11
53 Runtime error 8 ms 3008 KB Execution killed with signal 11
54 Runtime error 7 ms 2904 KB Execution killed with signal 11
55 Runtime error 7 ms 2900 KB Execution killed with signal 11
56 Runtime error 6 ms 2900 KB Execution killed with signal 11
57 Runtime error 6 ms 2952 KB Execution killed with signal 11
58 Runtime error 7 ms 3028 KB Execution killed with signal 11
59 Runtime error 6 ms 2912 KB Execution killed with signal 11
60 Runtime error 6 ms 2984 KB Execution killed with signal 11
61 Runtime error 6 ms 2900 KB Execution killed with signal 11
62 Runtime error 8 ms 2904 KB Execution killed with signal 11
63 Runtime error 7 ms 2904 KB Execution killed with signal 11
64 Execution timed out 1080 ms 1748 KB Time limit exceeded
65 Runtime error 6 ms 2900 KB Execution killed with signal 11
66 Runtime error 6 ms 2928 KB Execution killed with signal 11
67 Runtime error 8 ms 2896 KB Execution killed with signal 11
68 Runtime error 7 ms 2896 KB Execution killed with signal 11
69 Runtime error 6 ms 3004 KB Execution killed with signal 11
70 Execution timed out 1079 ms 1728 KB Time limit exceeded
71 Execution timed out 1072 ms 1748 KB Time limit exceeded
72 Execution timed out 1071 ms 1748 KB Time limit exceeded
73 Execution timed out 1053 ms 1724 KB Time limit exceeded
74 Execution timed out 1071 ms 1740 KB Time limit exceeded
75 Execution timed out 1081 ms 1748 KB Time limit exceeded
76 Execution timed out 1072 ms 1740 KB Time limit exceeded
77 Execution timed out 1080 ms 1748 KB Time limit exceeded
78 Execution timed out 1073 ms 1692 KB Time limit exceeded
79 Execution timed out 1069 ms 1808 KB Time limit exceeded
80 Execution timed out 1083 ms 1752 KB Time limit exceeded
81 Execution timed out 1080 ms 1748 KB Time limit exceeded
82 Execution timed out 1070 ms 1772 KB Time limit exceeded
83 Execution timed out 1076 ms 1748 KB Time limit exceeded
84 Execution timed out 1082 ms 1748 KB Time limit exceeded
85 Execution timed out 1084 ms 1748 KB Time limit exceeded
86 Runtime error 6 ms 2984 KB Execution killed with signal 11
87 Execution timed out 1084 ms 1756 KB Time limit exceeded
88 Execution timed out 1075 ms 1740 KB Time limit exceeded
89 Runtime error 6 ms 2892 KB Execution killed with signal 11
90 Runtime error 6 ms 2904 KB Execution killed with signal 11
91 Execution timed out 1066 ms 1736 KB Time limit exceeded
92 Execution timed out 1068 ms 1740 KB Time limit exceeded
93 Runtime error 7 ms 2900 KB Execution killed with signal 11
94 Runtime error 7 ms 2900 KB Execution killed with signal 11
95 Execution timed out 1079 ms 1756 KB Time limit exceeded
96 Execution timed out 1070 ms 1740 KB Time limit exceeded
97 Runtime error 7 ms 2896 KB Execution killed with signal 11
98 Execution timed out 1064 ms 1740 KB Time limit exceeded
99 Runtime error 6 ms 2900 KB Execution killed with signal 11
100 Runtime error 7 ms 2912 KB Execution killed with signal 11