oj.uz

Submission #832220

# Submission time Handle Problem Language Result Execution time Memory
832220 2023-08-21T06:59:47 Z vjudge1 Bomb (IZhO17_bomb) C++14
24 / 100
 178 ms 118128 KB 
#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
#define rep(i,n,N) for(int i = n; i<=N; ++i)
#define rap(i,n,N) for(int i = n; i>=N; --i)
#define For(i,n,N) for(int i = n; i< N; ++i)
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define mems(x,y) memset(x,y,sizeof x)
#define ari(x) array<int,x>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second
const int MAX = 2500 + 5;
mt19937 rng(99);

int n,m,mnr,mnc,cnt,y[MAX][MAX],z[MAX][MAX];
char c;
bool x[MAX][MAX];

inline bool cek(int r,int c,int dr,int dc){
	return y[r][c] - y[r-dr][c] - y[r][c-dc] + y[r-dr][c-dc] == dr*dc;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	mnr = n, mnc = m;
	rep(i,1,n){
		rep(j,1,m){
			cin>>c;
			x[i][j] = c=='1';
			y[i][j] = y[i-1][j]+y[i][j-1]-y[i-1][j-1]+x[i][j];
			if(x[i][j])++cnt;
			else if(cnt)mnc = min(mnc, cnt), cnt = 0;
		}
		if(cnt)mnc = min(mnc, cnt), cnt = 0;
	}
	rep(j,1,m){
		rep(i,1,n){
			if(x[i][j])++cnt;
			else if(cnt)mnr = min(mnr, cnt), cnt = 0;
		}
		if(cnt)mnr = min(mnr, cnt), cnt = 0;
	}
	rep(i,mnr,n)rep(j,mnc,m)if(x[i][j] && cek(i,j,mnr,mnc)){
		z[i][j]++;
		z[i-mnr][j]--;
		z[i][j-mnc]--;
		z[i-mnr][j-mnc]++;
	}
	rap(i,n,1)rap(j,m,1)z[i][j]+= z[i+1][j]+z[i][j+1]-z[i+1][j+1];
	rep(i,1,n){
//		if(i==1)cout<<"--------------\n";
//		rep(j,1,m)cout<<z[i][j];
//		cout<<endl;
		rep(j,1,m){
			assert((!!z[i][j])==x[i][j]);
		}
	}
	cout<<mnr*mnc<<endl;
	return 0;
}

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 11 ms 26436 KB Output is correct
4 Correct 12 ms 26452 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Runtime error 2 ms 852 KB Execution killed with signal 6
9 Runtime error 2 ms 852 KB Execution killed with signal 6
10 Runtime error 2 ms 724 KB Execution killed with signal 6
11 Runtime error 2 ms 852 KB Execution killed with signal 6
12 Runtime error 2 ms 852 KB Execution killed with signal 6
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Runtime error 2 ms 852 KB Execution killed with signal 6
16 Correct 0 ms 468 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Runtime error 5 ms 2004 KB Execution killed with signal 6
19 Runtime error 4 ms 2644 KB Execution killed with signal 6
20 Runtime error 4 ms 2512 KB Execution killed with signal 6
21 Runtime error 3 ms 1748 KB Execution killed with signal 6
22 Runtime error 4 ms 2260 KB Execution killed with signal 6
23 Runtime error 4 ms 2772 KB Execution killed with signal 6
24 Runtime error 4 ms 2256 KB Execution killed with signal 6
25 Runtime error 4 ms 2772 KB Execution killed with signal 6
26 Correct 1 ms 1492 KB Output is correct
27 Correct 3 ms 4052 KB Output is correct
28 Runtime error 11 ms 8532 KB Execution killed with signal 6
29 Runtime error 14 ms 10844 KB Execution killed with signal 6
30 Runtime error 17 ms 12880 KB Execution killed with signal 6
31 Runtime error 17 ms 10068 KB Execution killed with signal 6
32 Runtime error 14 ms 11712 KB Execution killed with signal 6
33 Runtime error 16 ms 13396 KB Execution killed with signal 6
34 Runtime error 12 ms 9428 KB Execution killed with signal 6
35 Runtime error 20 ms 13524 KB Execution killed with signal 6
36 Correct 6 ms 6840 KB Output is correct
37 Runtime error 2 ms 852 KB Execution killed with signal 6
38 Correct 103 ms 61084 KB Output is correct
39 Runtime error 2 ms 852 KB Execution killed with signal 6
40 Runtime error 38 ms 32004 KB Execution killed with signal 6
41 Runtime error 2 ms 852 KB Execution killed with signal 6
42 Runtime error 4 ms 2772 KB Execution killed with signal 6
43 Correct 106 ms 61044 KB Output is correct
44 Runtime error 16 ms 13444 KB Execution killed with signal 6
45 Runtime error 142 ms 117908 KB Execution killed with signal 6
46 Correct 112 ms 61092 KB Output is correct
47 Runtime error 145 ms 117968 KB Execution killed with signal 6
48 Runtime error 149 ms 117980 KB Execution killed with signal 6
49 Correct 110 ms 61216 KB Output is correct
50 Runtime error 157 ms 117896 KB Execution killed with signal 6
51 Runtime error 150 ms 117940 KB Execution killed with signal 6
52 Runtime error 150 ms 117988 KB Execution killed with signal 6
53 Runtime error 149 ms 117980 KB Execution killed with signal 6
54 Runtime error 146 ms 117880 KB Execution killed with signal 6
55 Runtime error 153 ms 117984 KB Execution killed with signal 6
56 Correct 101 ms 61004 KB Output is correct
57 Runtime error 149 ms 117916 KB Execution killed with signal 6
58 Runtime error 151 ms 117904 KB Execution killed with signal 6
59 Runtime error 164 ms 117872 KB Execution killed with signal 6
60 Correct 105 ms 60984 KB Output is correct
61 Correct 111 ms 61084 KB Output is correct
62 Correct 103 ms 61080 KB Output is correct
63 Correct 100 ms 61012 KB Output is correct
64 Correct 112 ms 61152 KB Output is correct
65 Runtime error 147 ms 117888 KB Execution killed with signal 6
66 Runtime error 143 ms 117924 KB Execution killed with signal 6
67 Runtime error 146 ms 117992 KB Execution killed with signal 6
68 Runtime error 152 ms 117976 KB Execution killed with signal 6
69 Runtime error 149 ms 117884 KB Execution killed with signal 6
70 Runtime error 116 ms 93900 KB Execution killed with signal 6
71 Runtime error 145 ms 117924 KB Execution killed with signal 6
72 Runtime error 150 ms 117972 KB Execution killed with signal 6
73 Runtime error 150 ms 117948 KB Execution killed with signal 6
74 Runtime error 144 ms 117884 KB Execution killed with signal 6
75 Runtime error 145 ms 118128 KB Execution killed with signal 6
76 Runtime error 146 ms 117968 KB Execution killed with signal 6
77 Runtime error 153 ms 117932 KB Execution killed with signal 6
78 Runtime error 149 ms 117976 KB Execution killed with signal 6
79 Runtime error 151 ms 117968 KB Execution killed with signal 6
80 Runtime error 155 ms 117860 KB Execution killed with signal 6
81 Runtime error 146 ms 117960 KB Execution killed with signal 6
82 Runtime error 149 ms 117996 KB Execution killed with signal 6
83 Runtime error 151 ms 117900 KB Execution killed with signal 6
84 Runtime error 158 ms 117952 KB Execution killed with signal 6
85 Runtime error 145 ms 117876 KB Execution killed with signal 6
86 Runtime error 153 ms 117992 KB Execution killed with signal 6
87 Runtime error 146 ms 117868 KB Execution killed with signal 6
88 Runtime error 145 ms 117972 KB Execution killed with signal 6
89 Runtime error 169 ms 117948 KB Execution killed with signal 6
90 Runtime error 107 ms 93784 KB Execution killed with signal 6
91 Runtime error 169 ms 117968 KB Execution killed with signal 6
92 Runtime error 143 ms 117964 KB Execution killed with signal 6
93 Runtime error 149 ms 117864 KB Execution killed with signal 6
94 Runtime error 159 ms 117884 KB Execution killed with signal 6
95 Runtime error 153 ms 117868 KB Execution killed with signal 6
96 Runtime error 150 ms 117860 KB Execution killed with signal 6
97 Runtime error 152 ms 117964 KB Execution killed with signal 6
98 Runtime error 161 ms 117872 KB Execution killed with signal 6
99 Runtime error 178 ms 117920 KB Execution killed with signal 6
100 Runtime error 166 ms 117876 KB Execution killed with signal 6