oj.uz

Submission #832287

# Submission time Handle Problem Language Result Execution time Memory
832287 2023-08-21T08:27:29 Z vjudge1 Bomb (IZhO17_bomb) C++14
10 / 100
 107 ms 34012 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(time(NULL));

int n,m,mnr,mnc,cnt,y[MAX][MAX],z[MAX][MAX];
char c;
bool x[MAX][MAX];
vector<ari(3)> v;

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;
}

inline bool solve(int dr,int dc){
	rep(i,1,n)rep(j,1,m)z[i][j] = 0;
	rep(i,dr,n)rep(j,dc,m)if(x[i][j] && cek(i,j,dr,dc)){
		z[i][j]++;
		z[i-dr][j]--;
		z[i][j-dc]--;
		z[i-dr][j-dc]++;
	}
	rap(i,n,1)rap(j,m,1){
		z[i][j]+= z[i+1][j]+z[i][j+1]-z[i+1][j+1];
		if((!!z[i][j])!=x[i][j])return 0;
	}
	return 1;
}

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;
	}
	if(n>450 || m>450)return 1;
	if(solve(mnr, mnc))return cout<<mnr*mnc<<endl,0;
	
	return 0;
}

Subtask #1
10.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 Runtime error 8 ms 16468 KB Execution failed because the return code was nonzero
4 Runtime error 8 ms 16460 KB Execution failed because the return code was nonzero
5 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
6 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 468 KB Output isn't correct
9 Incorrect 1 ms 468 KB Output isn't correct
10 Incorrect 1 ms 468 KB Output isn't correct
11 Incorrect 1 ms 468 KB Output isn't correct
12 Incorrect 0 ms 468 KB Output isn't correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Incorrect 1 ms 468 KB Output isn't correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Incorrect 1 ms 1100 KB Output isn't correct
19 Incorrect 1 ms 1364 KB Output isn't correct
20 Incorrect 1 ms 1364 KB Output isn't correct
21 Incorrect 1 ms 852 KB Output isn't correct
22 Incorrect 1 ms 1108 KB Output isn't correct
23 Incorrect 1 ms 1492 KB Output isn't correct
24 Incorrect 1 ms 1240 KB Output isn't correct
25 Incorrect 1 ms 1492 KB Output isn't correct
26 Correct 1 ms 1492 KB Output is correct
27 Correct 3 ms 4052 KB Output is correct
28 Incorrect 3 ms 4308 KB Output isn't correct
29 Incorrect 4 ms 5460 KB Output isn't correct
30 Incorrect 7 ms 6476 KB Output isn't correct
31 Incorrect 6 ms 5076 KB Output isn't correct
32 Incorrect 4 ms 5972 KB Output isn't correct
33 Incorrect 6 ms 6740 KB Output isn't correct
34 Incorrect 3 ms 4692 KB Output isn't correct
35 Incorrect 6 ms 6744 KB Output isn't correct
36 Correct 6 ms 6808 KB Output is correct
37 Incorrect 1 ms 468 KB Output isn't correct
38 Runtime error 86 ms 33832 KB Execution failed because the return code was nonzero
39 Incorrect 0 ms 460 KB Output isn't correct
40 Runtime error 12 ms 9684 KB Execution failed because the return code was nonzero
41 Incorrect 1 ms 464 KB Output isn't correct
42 Incorrect 1 ms 1492 KB Output isn't correct
43 Runtime error 85 ms 33824 KB Execution failed because the return code was nonzero
44 Incorrect 6 ms 6740 KB Output isn't correct
45 Runtime error 84 ms 33788 KB Execution failed because the return code was nonzero
46 Runtime error 92 ms 33816 KB Execution failed because the return code was nonzero
47 Runtime error 89 ms 34012 KB Execution failed because the return code was nonzero
48 Runtime error 84 ms 33740 KB Execution failed because the return code was nonzero
49 Runtime error 86 ms 33748 KB Execution failed because the return code was nonzero
50 Runtime error 86 ms 33744 KB Execution failed because the return code was nonzero
51 Runtime error 83 ms 33800 KB Execution failed because the return code was nonzero
52 Runtime error 87 ms 33828 KB Execution failed because the return code was nonzero
53 Runtime error 83 ms 33752 KB Execution failed because the return code was nonzero
54 Runtime error 83 ms 33780 KB Execution failed because the return code was nonzero
55 Runtime error 93 ms 33820 KB Execution failed because the return code was nonzero
56 Runtime error 88 ms 33856 KB Execution failed because the return code was nonzero
57 Runtime error 89 ms 33776 KB Execution failed because the return code was nonzero
58 Runtime error 86 ms 33932 KB Execution failed because the return code was nonzero
59 Runtime error 86 ms 33768 KB Execution failed because the return code was nonzero
60 Runtime error 102 ms 33832 KB Execution failed because the return code was nonzero
61 Runtime error 89 ms 33800 KB Execution failed because the return code was nonzero
62 Runtime error 83 ms 33852 KB Execution failed because the return code was nonzero
63 Runtime error 85 ms 33760 KB Execution failed because the return code was nonzero
64 Runtime error 93 ms 33828 KB Execution failed because the return code was nonzero
65 Runtime error 85 ms 33844 KB Execution failed because the return code was nonzero
66 Runtime error 85 ms 33824 KB Execution failed because the return code was nonzero
67 Runtime error 83 ms 33836 KB Execution failed because the return code was nonzero
68 Runtime error 86 ms 33752 KB Execution failed because the return code was nonzero
69 Runtime error 84 ms 33868 KB Execution failed because the return code was nonzero
70 Runtime error 58 ms 27204 KB Execution failed because the return code was nonzero
71 Runtime error 89 ms 33808 KB Execution failed because the return code was nonzero
72 Runtime error 93 ms 33788 KB Execution failed because the return code was nonzero
73 Runtime error 87 ms 33768 KB Execution failed because the return code was nonzero
74 Runtime error 107 ms 33752 KB Execution failed because the return code was nonzero
75 Runtime error 90 ms 33764 KB Execution failed because the return code was nonzero
76 Runtime error 84 ms 33864 KB Execution failed because the return code was nonzero
77 Runtime error 82 ms 33740 KB Execution failed because the return code was nonzero
78 Runtime error 86 ms 33756 KB Execution failed because the return code was nonzero
79 Runtime error 96 ms 33860 KB Execution failed because the return code was nonzero
80 Runtime error 85 ms 33872 KB Execution failed because the return code was nonzero
81 Runtime error 83 ms 33852 KB Execution failed because the return code was nonzero
82 Runtime error 83 ms 33796 KB Execution failed because the return code was nonzero
83 Runtime error 84 ms 33868 KB Execution failed because the return code was nonzero
84 Runtime error 84 ms 33848 KB Execution failed because the return code was nonzero
85 Runtime error 85 ms 33812 KB Execution failed because the return code was nonzero
86 Runtime error 88 ms 33784 KB Execution failed because the return code was nonzero
87 Runtime error 84 ms 33864 KB Execution failed because the return code was nonzero
88 Runtime error 83 ms 33776 KB Execution failed because the return code was nonzero
89 Runtime error 84 ms 33740 KB Execution failed because the return code was nonzero
90 Runtime error 56 ms 27188 KB Execution failed because the return code was nonzero
91 Runtime error 82 ms 33864 KB Execution failed because the return code was nonzero
92 Runtime error 82 ms 33804 KB Execution failed because the return code was nonzero
93 Runtime error 82 ms 33764 KB Execution failed because the return code was nonzero
94 Runtime error 84 ms 33868 KB Execution failed because the return code was nonzero
95 Runtime error 82 ms 33880 KB Execution failed because the return code was nonzero
96 Runtime error 86 ms 33916 KB Execution failed because the return code was nonzero
97 Runtime error 88 ms 33768 KB Execution failed because the return code was nonzero
98 Runtime error 82 ms 33756 KB Execution failed because the return code was nonzero
99 Runtime error 82 ms 33868 KB Execution failed because the return code was nonzero
100 Runtime error 87 ms 33956 KB Execution failed because the return code was nonzero