oj.uz

Submission #832290

# Submission time Handle Problem Language Result Execution time Memory
832290 2023-08-21T08:29:29 Z vjudge1 Bomb (IZhO17_bomb) C++14
37 / 100
 103 ms 30956 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],ans;
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;
	ans = mnc;
	rep(i,2,mnr){
		while(i*mnc>ans && !solve(i, mnc))--mnc;
		ans = max(ans, i*mnc);
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
37.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 Runtime error 7 ms 16448 KB Execution failed because the return code was nonzero
4 Runtime error 8 ms 16468 KB Execution failed because the return code was nonzero
5 Runtime error 0 ms 340 KB Execution failed because the return code was nonzero
6 Runtime error 0 ms 340 KB Execution failed because the return code was nonzero
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 1108 KB Output is correct
19 Correct 1 ms 1364 KB Output is correct
20 Correct 1 ms 1364 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 1 ms 1108 KB Output is correct
23 Correct 1 ms 1364 KB Output is correct
24 Correct 1 ms 1236 KB Output is correct
25 Correct 2 ms 1368 KB Output is correct
26 Correct 1 ms 1364 KB Output is correct
27 Correct 4 ms 4052 KB Output is correct
28 Correct 6 ms 4180 KB Output is correct
29 Correct 29 ms 5332 KB Output is correct
30 Correct 43 ms 6228 KB Output is correct
31 Correct 34 ms 4948 KB Output is correct
32 Correct 19 ms 5716 KB Output is correct
33 Correct 51 ms 6612 KB Output is correct
34 Correct 7 ms 4692 KB Output is correct
35 Correct 53 ms 6612 KB Output is correct
36 Correct 5 ms 6588 KB Output is correct
37 Correct 0 ms 468 KB Output is correct
38 Runtime error 101 ms 30916 KB Execution failed because the return code was nonzero
39 Correct 0 ms 468 KB Output is correct
40 Runtime error 12 ms 8916 KB Execution failed because the return code was nonzero
41 Correct 0 ms 468 KB Output is correct
42 Correct 2 ms 1364 KB Output is correct
43 Runtime error 78 ms 30912 KB Execution failed because the return code was nonzero
44 Correct 83 ms 6612 KB Output is correct
45 Runtime error 80 ms 30928 KB Execution failed because the return code was nonzero
46 Runtime error 83 ms 30916 KB Execution failed because the return code was nonzero
47 Runtime error 81 ms 30924 KB Execution failed because the return code was nonzero
48 Runtime error 78 ms 30916 KB Execution failed because the return code was nonzero
49 Runtime error 82 ms 30880 KB Execution failed because the return code was nonzero
50 Runtime error 79 ms 30952 KB Execution failed because the return code was nonzero
51 Runtime error 79 ms 30892 KB Execution failed because the return code was nonzero
52 Runtime error 80 ms 30840 KB Execution failed because the return code was nonzero
53 Runtime error 99 ms 30900 KB Execution failed because the return code was nonzero
54 Runtime error 80 ms 30892 KB Execution failed because the return code was nonzero
55 Runtime error 79 ms 30844 KB Execution failed because the return code was nonzero
56 Runtime error 81 ms 30932 KB Execution failed because the return code was nonzero
57 Runtime error 79 ms 30908 KB Execution failed because the return code was nonzero
58 Runtime error 80 ms 30940 KB Execution failed because the return code was nonzero
59 Runtime error 79 ms 30956 KB Execution failed because the return code was nonzero
60 Runtime error 81 ms 30860 KB Execution failed because the return code was nonzero
61 Runtime error 79 ms 30924 KB Execution failed because the return code was nonzero
62 Runtime error 79 ms 30908 KB Execution failed because the return code was nonzero
63 Runtime error 79 ms 30916 KB Execution failed because the return code was nonzero
64 Runtime error 80 ms 30952 KB Execution failed because the return code was nonzero
65 Runtime error 82 ms 30940 KB Execution failed because the return code was nonzero
66 Runtime error 97 ms 30844 KB Execution failed because the return code was nonzero
67 Runtime error 79 ms 30892 KB Execution failed because the return code was nonzero
68 Runtime error 80 ms 30940 KB Execution failed because the return code was nonzero
69 Runtime error 78 ms 30872 KB Execution failed because the return code was nonzero
70 Runtime error 56 ms 24776 KB Execution failed because the return code was nonzero
71 Runtime error 81 ms 30924 KB Execution failed because the return code was nonzero
72 Runtime error 80 ms 30924 KB Execution failed because the return code was nonzero
73 Runtime error 79 ms 30948 KB Execution failed because the return code was nonzero
74 Runtime error 78 ms 30924 KB Execution failed because the return code was nonzero
75 Runtime error 79 ms 30952 KB Execution failed because the return code was nonzero
76 Runtime error 79 ms 30852 KB Execution failed because the return code was nonzero
77 Runtime error 84 ms 30940 KB Execution failed because the return code was nonzero
78 Runtime error 103 ms 30916 KB Execution failed because the return code was nonzero
79 Runtime error 80 ms 30848 KB Execution failed because the return code was nonzero
80 Runtime error 80 ms 30840 KB Execution failed because the return code was nonzero
81 Runtime error 81 ms 30840 KB Execution failed because the return code was nonzero
82 Runtime error 85 ms 30856 KB Execution failed because the return code was nonzero
83 Runtime error 79 ms 30924 KB Execution failed because the return code was nonzero
84 Runtime error 78 ms 30928 KB Execution failed because the return code was nonzero
85 Runtime error 98 ms 30924 KB Execution failed because the return code was nonzero
86 Runtime error 80 ms 30928 KB Execution failed because the return code was nonzero
87 Runtime error 80 ms 30880 KB Execution failed because the return code was nonzero
88 Runtime error 79 ms 30872 KB Execution failed because the return code was nonzero
89 Runtime error 89 ms 30928 KB Execution failed because the return code was nonzero
90 Runtime error 53 ms 24724 KB Execution failed because the return code was nonzero
91 Runtime error 78 ms 30852 KB Execution failed because the return code was nonzero
92 Runtime error 99 ms 30916 KB Execution failed because the return code was nonzero
93 Runtime error 80 ms 30892 KB Execution failed because the return code was nonzero
94 Runtime error 79 ms 30956 KB Execution failed because the return code was nonzero
95 Runtime error 79 ms 30872 KB Execution failed because the return code was nonzero
96 Runtime error 86 ms 30844 KB Execution failed because the return code was nonzero
97 Runtime error 87 ms 30888 KB Execution failed because the return code was nonzero
98 Runtime error 81 ms 30920 KB Execution failed because the return code was nonzero
99 Runtime error 81 ms 30880 KB Execution failed because the return code was nonzero
100 Runtime error 82 ms 30916 KB Execution failed because the return code was nonzero