QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#370797#6746. Merge the RectanglesLysusWA 26ms31740kbC++201.7kb2024-03-29 16:39:082024-03-29 16:39:12

Judging History

你现在查看的是最新测评结果

  • [2024-03-29 16:39:12]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:31740kb
  • [2024-03-29 16:39:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2010;

int n, m, sum[2][N][N];
string a[N], b[N];

void solve() {
	cin >> n >> m;
	int Idx = 0, cnt = 0;
	for(int i = 1; i < n; ++i) {
		cin >> a[i];
		a[i] = " " + a[i];
	}
	for(int i = 1; i < n; ++i) {
		for(int j = 1; j <= m; ++j) {
			sum[0][i][j] = sum[0][i][j - 1] + (a[i][j] == '1');
		}
	}
	for(int i = 1; i <= n; ++i) {
		cin >> b[i];
		b[i] = " " + b[i];
	}
	for(int j = 1; j < m; ++j) {
		for(int i = 1; i <= n; ++i) {
			sum[1][i][j] = sum[1][i - 1][j] + (b[i][j] == '1');
		}
	}
	auto work = [&](auto self, int x1, int y1, int x2, int y2) -> int {
		int flag = 1, cnt = 0, mark = 0;
		if(x1 >= x2 || y1 >= y2) return 1;
		if(x1 < 1 || x2 > n || y1 < 1 || y2 > m) return 1;
		for(int i = x1; i < x2; ++i) {
			cnt += sum[0][i][y2] - sum[0][i][y1 - 1];
			if(sum[0][i][y2] - sum[0][i][y1 - 1] == y2 - y1 + 1) {
				mark = 1;
				flag &= self(self, x1, y1, i - 1, y2);
				flag &= self(self, i + 1, y1, x2, y2);
				break;
			}
		}
		if(!mark) {
			for(int j = y1; j < y2; ++j) {
				cnt += sum[1][x2][j] - sum[1][x1][j - 1];
				if(sum[1][x2][j] - sum[1][x1][j - 1] == x2 - x1 + 1) {
					mark = 1;
					flag &= self(self, x1, y1, x2, j - 1);
					flag &= self(self, x1, j + 1, x2, y2);
					break;
				}
			}
		}
//		cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << mark << " " << cnt << '\n';
		if(!mark && cnt) return 0;
		else return flag;
	};
	int flag = work(work, 1, 1, n, m);
	if(flag) cout << "YES\n";
	else cout << "NO\n"; 
}
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
/*
3 3
111
111
11
11
11
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3808kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 26ms
memory: 31620kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 17ms
memory: 31700kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 7ms
memory: 31740kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: -100
Wrong Answer
time: 4ms
memory: 31620kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

NO

result:

wrong answer expected YES, found NO