oj.uz

Submission #935444

# Submission time Handle Problem Language Result Execution time Memory
935444 2024-02-29T05:39:44 Z Darren0724 Bomb (IZhO17_bomb) C++17
41 / 100
 1000 ms 80988 KB 
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx","avx2")
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
int32_t main() {
    LCBorz;
    int n,m;cin>>n>>m;
    vector<vector<int>> v(n+1,vector<int>(m+1,0)),v1(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;cin>>c;
            v[i][j]=v1[i][j]=(c=='0');
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v1[i][j]+=v1[i-1][j]+v1[i][j-1]-v1[i-1][j-1];
        }
    }
    int ans=0;
    int last=0;
    auto check=[&](int a,int b)->int {
        vector<vector<int>> pre(n+2,vector<int>(m+2,0));
        for(int i=a;i<=n;i++){
            for(int j=b;j<=m;j++){
                if(v1[i][j]-v1[i][j-b]-v1[i-a][j]+v1[i-a][j-b]==0){
                    pre[i-a+1][j-b+1]++;
                    pre[i+1][j-b+1]--;
                    pre[i-a+1][j+1]--;
                    pre[i+1][j+1]++;
                }
            }
        }
        int flag=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                pre[i][j]+=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
                if(v[i][j]==0&&pre[i][j]==0){
                    flag=0;
                }
            }
        }
        return flag;
    };
    for(int i=n;i>=1;i--){
        while(last+1<=m&&check(i,last+1)){
            last++;
        }
        ans=max(ans,last*i);
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
41.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 220 ms 860 KB Output is correct
4 Correct 204 ms 860 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 2 ms 500 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 2 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 3 ms 604 KB Output is correct
24 Correct 2 ms 548 KB Output is correct
25 Correct 4 ms 348 KB Output is correct
26 Correct 3 ms 348 KB Output is correct
27 Correct 73 ms 2488 KB Output is correct
28 Correct 88 ms 1912 KB Output is correct
29 Correct 175 ms 2092 KB Output is correct
30 Correct 296 ms 3148 KB Output is correct
31 Correct 194 ms 2816 KB Output is correct
32 Correct 244 ms 2908 KB Output is correct
33 Correct 347 ms 3096 KB Output is correct
34 Correct 83 ms 1544 KB Output is correct
35 Correct 335 ms 3096 KB Output is correct
36 Correct 315 ms 3232 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Execution timed out 1012 ms 80604 KB Time limit exceeded
39 Correct 0 ms 348 KB Output is correct
40 Execution timed out 1091 ms 10912 KB Time limit exceeded
41 Correct 0 ms 348 KB Output is correct
42 Correct 4 ms 596 KB Output is correct
43 Execution timed out 1030 ms 80460 KB Time limit exceeded
44 Correct 378 ms 3096 KB Output is correct
45 Execution timed out 1039 ms 80744 KB Time limit exceeded
46 Execution timed out 1071 ms 80556 KB Time limit exceeded
47 Execution timed out 1018 ms 80420 KB Time limit exceeded
48 Execution timed out 1060 ms 80668 KB Time limit exceeded
49 Execution timed out 1055 ms 80512 KB Time limit exceeded
50 Execution timed out 1054 ms 80432 KB Time limit exceeded
51 Execution timed out 1066 ms 80616 KB Time limit exceeded
52 Execution timed out 1049 ms 80768 KB Time limit exceeded
53 Execution timed out 1051 ms 80912 KB Time limit exceeded
54 Execution timed out 1035 ms 80636 KB Time limit exceeded
55 Execution timed out 1012 ms 80672 KB Time limit exceeded
56 Execution timed out 1039 ms 80544 KB Time limit exceeded
57 Execution timed out 1032 ms 80544 KB Time limit exceeded
58 Execution timed out 1016 ms 80680 KB Time limit exceeded
59 Execution timed out 1062 ms 80436 KB Time limit exceeded
60 Execution timed out 1054 ms 80412 KB Time limit exceeded
61 Execution timed out 1055 ms 80632 KB Time limit exceeded
62 Execution timed out 1066 ms 80420 KB Time limit exceeded
63 Execution timed out 1055 ms 80628 KB Time limit exceeded
64 Execution timed out 1035 ms 80988 KB Time limit exceeded
65 Execution timed out 1060 ms 80420 KB Time limit exceeded
66 Execution timed out 1055 ms 80492 KB Time limit exceeded
67 Execution timed out 1106 ms 80656 KB Time limit exceeded
68 Execution timed out 1031 ms 80840 KB Time limit exceeded
69 Execution timed out 1054 ms 80552 KB Time limit exceeded
70 Execution timed out 1056 ms 51820 KB Time limit exceeded
71 Execution timed out 1067 ms 80488 KB Time limit exceeded
72 Execution timed out 1027 ms 80596 KB Time limit exceeded
73 Execution timed out 1052 ms 80616 KB Time limit exceeded
74 Execution timed out 1025 ms 80512 KB Time limit exceeded
75 Execution timed out 1066 ms 80696 KB Time limit exceeded
76 Execution timed out 1050 ms 80580 KB Time limit exceeded
77 Execution timed out 1042 ms 80672 KB Time limit exceeded
78 Execution timed out 1067 ms 80656 KB Time limit exceeded
79 Execution timed out 1016 ms 80604 KB Time limit exceeded
80 Execution timed out 1061 ms 80504 KB Time limit exceeded
81 Execution timed out 1087 ms 80388 KB Time limit exceeded
82 Execution timed out 1029 ms 80620 KB Time limit exceeded
83 Execution timed out 1034 ms 80460 KB Time limit exceeded
84 Execution timed out 1103 ms 80512 KB Time limit exceeded
85 Execution timed out 1029 ms 80676 KB Time limit exceeded
86 Execution timed out 1048 ms 80384 KB Time limit exceeded
87 Execution timed out 1097 ms 80468 KB Time limit exceeded
88 Execution timed out 1039 ms 80532 KB Time limit exceeded
89 Execution timed out 1055 ms 80384 KB Time limit exceeded
90 Execution timed out 1028 ms 51828 KB Time limit exceeded
91 Execution timed out 1061 ms 80544 KB Time limit exceeded
92 Execution timed out 1042 ms 80548 KB Time limit exceeded
93 Execution timed out 1018 ms 80852 KB Time limit exceeded
94 Execution timed out 1040 ms 80500 KB Time limit exceeded
95 Execution timed out 1068 ms 80496 KB Time limit exceeded
96 Execution timed out 1055 ms 80496 KB Time limit exceeded
97 Execution timed out 1081 ms 80392 KB Time limit exceeded
98 Execution timed out 1085 ms 80568 KB Time limit exceeded
99 Execution timed out 1018 ms 80404 KB Time limit exceeded
100 Execution timed out 1026 ms 80576 KB Time limit exceeded