oj.uz

답안 #832655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832655 2023-08-21T13:04:12 Z vjudge1 Bomb (IZhO17_bomb) C++14
51 / 100
 1000 ms 61704 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)mems(z[i], 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(solve(mnr, mnc))return cout<<mnr*mnc<<endl,0;
	int k = min(mnr, mnc);
	while(!solve(k, k))--k;
	int r,c;
	r = c = k;
	while(solve(r+1, c))++r;
	while(solve(r, c+1))++c;
	cout<<r*c<<endl;
	return 0;
}

Subtask #1
51.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 18 ms 40984 KB Output is correct
4 Correct 22 ms 40928 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 1360 KB Output is correct
18 Correct 1 ms 1492 KB Output is correct
19 Correct 2 ms 1876 KB Output is correct
20 Correct 2 ms 1876 KB Output is correct
21 Correct 1 ms 1236 KB Output is correct
22 Correct 1 ms 1616 KB Output is correct
23 Correct 2 ms 2004 KB Output is correct
24 Correct 1 ms 1620 KB Output is correct
25 Correct 2 ms 2004 KB Output is correct
26 Correct 1 ms 2004 KB Output is correct
27 Correct 4 ms 5460 KB Output is correct
28 Correct 6 ms 5588 KB Output is correct
29 Incorrect 16 ms 7296 KB Output isn't correct
30 Correct 38 ms 8276 KB Output is correct
31 Correct 24 ms 6516 KB Output is correct
32 Correct 19 ms 7640 KB Output is correct
33 Correct 94 ms 8660 KB Output is correct
34 Correct 5 ms 6484 KB Output is correct
35 Correct 43 ms 8660 KB Output is correct
36 Correct 7 ms 8604 KB Output is correct
37 Incorrect 1 ms 596 KB Output isn't correct
38 Correct 99 ms 61476 KB Output is correct
39 Incorrect 1 ms 596 KB Output isn't correct
40 Incorrect 230 ms 18340 KB Output isn't correct
41 Incorrect 1 ms 588 KB Output isn't correct
42 Incorrect 3 ms 2004 KB Output isn't correct
43 Correct 107 ms 61512 KB Output is correct
44 Incorrect 39 ms 8660 KB Output isn't correct
45 Execution timed out 1082 ms 61532 KB Time limit exceeded
46 Correct 109 ms 61544 KB Output is correct
47 Execution timed out 1090 ms 61464 KB Time limit exceeded
48 Correct 801 ms 61508 KB Output is correct
49 Correct 110 ms 61608 KB Output is correct
50 Execution timed out 1088 ms 61532 KB Time limit exceeded
51 Execution timed out 1074 ms 61524 KB Time limit exceeded
52 Execution timed out 1079 ms 61520 KB Time limit exceeded
53 Execution timed out 1081 ms 61592 KB Time limit exceeded
54 Correct 662 ms 61704 KB Output is correct
55 Correct 355 ms 61564 KB Output is correct
56 Correct 98 ms 61508 KB Output is correct
57 Execution timed out 1078 ms 61524 KB Time limit exceeded
58 Execution timed out 1045 ms 61552 KB Time limit exceeded
59 Correct 516 ms 61588 KB Output is correct
60 Correct 126 ms 61472 KB Output is correct
61 Correct 106 ms 61588 KB Output is correct
62 Correct 107 ms 61528 KB Output is correct
63 Correct 111 ms 61524 KB Output is correct
64 Correct 101 ms 61584 KB Output is correct
65 Correct 779 ms 61588 KB Output is correct
66 Execution timed out 1062 ms 61516 KB Time limit exceeded
67 Execution timed out 1060 ms 61548 KB Time limit exceeded
68 Execution timed out 1086 ms 61528 KB Time limit exceeded
69 Execution timed out 1083 ms 61556 KB Time limit exceeded
70 Execution timed out 1044 ms 48256 KB Time limit exceeded
71 Execution timed out 1079 ms 61520 KB Time limit exceeded
72 Execution timed out 1081 ms 61484 KB Time limit exceeded
73 Execution timed out 1080 ms 61476 KB Time limit exceeded
74 Execution timed out 1073 ms 61536 KB Time limit exceeded
75 Execution timed out 1077 ms 61532 KB Time limit exceeded
76 Execution timed out 1082 ms 61516 KB Time limit exceeded
77 Execution timed out 1074 ms 61508 KB Time limit exceeded
78 Execution timed out 1072 ms 61584 KB Time limit exceeded
79 Correct 735 ms 61584 KB Output is correct
80 Execution timed out 1084 ms 61520 KB Time limit exceeded
81 Execution timed out 1029 ms 61532 KB Time limit exceeded
82 Execution timed out 1068 ms 61516 KB Time limit exceeded
83 Execution timed out 1081 ms 61548 KB Time limit exceeded
84 Execution timed out 1074 ms 61528 KB Time limit exceeded
85 Execution timed out 1076 ms 61520 KB Time limit exceeded
86 Execution timed out 1082 ms 61460 KB Time limit exceeded
87 Execution timed out 1074 ms 61532 KB Time limit exceeded
88 Execution timed out 1084 ms 61516 KB Time limit exceeded
89 Execution timed out 1087 ms 61548 KB Time limit exceeded
90 Execution timed out 1076 ms 48316 KB Time limit exceeded
91 Execution timed out 1077 ms 61624 KB Time limit exceeded
92 Execution timed out 1084 ms 61520 KB Time limit exceeded
93 Execution timed out 1090 ms 61476 KB Time limit exceeded
94 Execution timed out 1074 ms 61532 KB Time limit exceeded
95 Execution timed out 1083 ms 61668 KB Time limit exceeded
96 Execution timed out 1065 ms 61584 KB Time limit exceeded
97 Execution timed out 1018 ms 61584 KB Time limit exceeded
98 Execution timed out 1072 ms 61532 KB Time limit exceeded
99 Execution timed out 1082 ms 61516 KB Time limit exceeded
100 Execution timed out 1075 ms 61528 KB Time limit exceeded