oj.uz

Submission #832224

# Submission time Handle Problem Language Result Execution time Memory
832224 2023-08-21T07:01:46 Z vjudge1 Bomb (IZhO17_bomb) C++14
24 / 100
 213 ms 112380 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){
			if((!!z[i][j])!=x[i][j]){
				assert(!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 0 ms 468 KB Output is correct
3 Correct 11 ms 26512 KB Output is correct
4 Correct 12 ms 26516 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 392 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 0 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Runtime error 2 ms 828 KB Execution killed with signal 6
16 Correct 0 ms 468 KB Output is correct
17 Correct 1 ms 1000 KB Output is correct
18 Runtime error 4 ms 2072 KB Execution killed with signal 6
19 Runtime error 4 ms 2644 KB Execution killed with signal 6
20 Runtime error 4 ms 2516 KB Execution killed with signal 6
21 Runtime error 3 ms 1748 KB Execution killed with signal 6
22 Runtime error 3 ms 2260 KB Execution killed with signal 6
23 Runtime error 4 ms 2772 KB Execution killed with signal 6
24 Runtime error 3 ms 2260 KB Execution killed with signal 6
25 Runtime error 5 ms 2772 KB Execution killed with signal 6
26 Correct 1 ms 1364 KB Output is correct
27 Correct 3 ms 4052 KB Output is correct
28 Runtime error 10 ms 8416 KB Execution killed with signal 6
29 Runtime error 13 ms 10784 KB Execution killed with signal 6
30 Runtime error 16 ms 12628 KB Execution killed with signal 6
31 Runtime error 12 ms 9996 KB Execution killed with signal 6
32 Runtime error 13 ms 11604 KB Execution killed with signal 6
33 Runtime error 16 ms 13248 KB Execution killed with signal 6
34 Runtime error 12 ms 9376 KB Execution killed with signal 6
35 Runtime error 16 ms 13268 KB Execution killed with signal 6
36 Correct 5 ms 6604 KB Output is correct
37 Runtime error 2 ms 852 KB Execution killed with signal 6
38 Correct 96 ms 55368 KB Output is correct
39 Runtime error 2 ms 852 KB Execution killed with signal 6
40 Runtime error 37 ms 31304 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 105 ms 55448 KB Output is correct
44 Runtime error 19 ms 13264 KB Execution killed with signal 6
45 Runtime error 140 ms 112256 KB Execution killed with signal 6
46 Correct 108 ms 55432 KB Output is correct
47 Runtime error 147 ms 112320 KB Execution killed with signal 6
48 Runtime error 144 ms 112332 KB Execution killed with signal 6
49 Correct 104 ms 55356 KB Output is correct
50 Runtime error 146 ms 112308 KB Execution killed with signal 6
51 Runtime error 149 ms 112324 KB Execution killed with signal 6
52 Runtime error 144 ms 112332 KB Execution killed with signal 6
53 Runtime error 159 ms 112336 KB Execution killed with signal 6
54 Runtime error 146 ms 112260 KB Execution killed with signal 6
55 Runtime error 149 ms 112340 KB Execution killed with signal 6
56 Correct 99 ms 55400 KB Output is correct
57 Runtime error 147 ms 112352 KB Execution killed with signal 6
58 Runtime error 150 ms 112340 KB Execution killed with signal 6
59 Runtime error 156 ms 112328 KB Execution killed with signal 6
60 Correct 105 ms 55456 KB Output is correct
61 Correct 103 ms 55372 KB Output is correct
62 Correct 104 ms 55380 KB Output is correct
63 Correct 98 ms 55372 KB Output is correct
64 Correct 102 ms 55384 KB Output is correct
65 Runtime error 145 ms 112240 KB Execution killed with signal 6
66 Runtime error 140 ms 112320 KB Execution killed with signal 6
67 Runtime error 178 ms 112252 KB Execution killed with signal 6
68 Runtime error 141 ms 112308 KB Execution killed with signal 6
69 Runtime error 146 ms 112352 KB Execution killed with signal 6
70 Runtime error 104 ms 89872 KB Execution killed with signal 6
71 Runtime error 145 ms 112352 KB Execution killed with signal 6
72 Runtime error 146 ms 112248 KB Execution killed with signal 6
73 Runtime error 141 ms 112312 KB Execution killed with signal 6
74 Runtime error 142 ms 112348 KB Execution killed with signal 6
75 Runtime error 144 ms 112328 KB Execution killed with signal 6
76 Runtime error 148 ms 112240 KB Execution killed with signal 6
77 Runtime error 143 ms 112324 KB Execution killed with signal 6
78 Runtime error 146 ms 112308 KB Execution killed with signal 6
79 Runtime error 141 ms 112248 KB Execution killed with signal 6
80 Runtime error 141 ms 112328 KB Execution killed with signal 6
81 Runtime error 144 ms 112272 KB Execution killed with signal 6
82 Runtime error 143 ms 112332 KB Execution killed with signal 6
83 Runtime error 144 ms 112284 KB Execution killed with signal 6
84 Runtime error 145 ms 112240 KB Execution killed with signal 6
85 Runtime error 186 ms 112256 KB Execution killed with signal 6
86 Runtime error 157 ms 112352 KB Execution killed with signal 6
87 Runtime error 143 ms 112228 KB Execution killed with signal 6
88 Runtime error 143 ms 112284 KB Execution killed with signal 6
89 Runtime error 142 ms 112344 KB Execution killed with signal 6
90 Runtime error 108 ms 89896 KB Execution killed with signal 6
91 Runtime error 213 ms 112296 KB Execution killed with signal 6
92 Runtime error 141 ms 112332 KB Execution killed with signal 6
93 Runtime error 182 ms 112300 KB Execution killed with signal 6
94 Runtime error 144 ms 112328 KB Execution killed with signal 6
95 Runtime error 148 ms 112380 KB Execution killed with signal 6
96 Runtime error 144 ms 112364 KB Execution killed with signal 6
97 Runtime error 162 ms 112284 KB Execution killed with signal 6
98 Runtime error 148 ms 112320 KB Execution killed with signal 6
99 Runtime error 147 ms 112356 KB Execution killed with signal 6
100 Runtime error 142 ms 112344 KB Execution killed with signal 6