QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#183571#6746. Merge the RectanglesdinzihanAC ✓60ms24508kbC++141.4kb2023-09-19 17:41:112023-09-19 17:41:11

Judging History

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

  • [2023-09-19 17:41:11]
  • 评测
  • 测评结果:AC
  • 用时:60ms
  • 内存:24508kb
  • [2023-09-19 17:41:11]
  • 提交

answer

#include <bits/stdc++.h>
#include <array>

using namespace std;
typedef long long ll;

const int N = 1600;

#define endl '\n'

int ma1[N][N];
int ma2[N][N];
bool vis[N][N];

bool flag;

inline void dfs(int top, int bot, int left, int right) {
	bool ok = false;
	for (int i = top + 1; i <= bot; i++) {
		if (ma1[i][right] - ma1[i][left - 1] != 0)ok = true;
		if (ma1[i][right] - ma1[i][left - 1] == right - left + 1) {
			dfs(top, i - 1, left, right);
			dfs(i, bot, left, right);
			return;
		}
	}
	for (int i = left + 1; i <= right; i++) {
		if (ma2[bot][i] - ma2[top-1][i] != 0)ok = true;
		if (ma2[bot][i] - ma2[top-1][i] == bot - top + 1) {
			dfs(top, bot, left, i - 1);
			dfs(top, bot, i, right);
			return;
		}
	}
	if (ok) flag = 1;
}

inline void solve() {
	ll n, m;
	cin >> n >> m;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char op;
			cin >> op;
			ma1[i][j] = op - '0';
			ma1[i][j] += ma1[i][j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 2; j <= m; j++) {
			char op;
			cin >> op;
			ma2[i][j] = op - '0';
			ma2[i][j] += ma2[i - 1][j];
		}
	}

	dfs(1, n, 1, m);

	if (flag)cout << "NO" << endl;
	else cout << "YES" << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t = 1;
	//cin >> t;
	for (int i = 1; i <= t; i++) {
		solve();
	}
	return 0;
}

/*
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

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

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 24ms
memory: 23212kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 47ms
memory: 24508kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 25ms
memory: 23632kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 36ms
memory: 23960kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #7:

score: 0
Accepted
time: 34ms
memory: 24416kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #8:

score: 0
Accepted
time: 37ms
memory: 24448kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #9:

score: 0
Accepted
time: 28ms
memory: 24056kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #10:

score: 0
Accepted
time: 48ms
memory: 23416kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #11:

score: 0
Accepted
time: 48ms
memory: 23840kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #12:

score: 0
Accepted
time: 48ms
memory: 24232kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #13:

score: 0
Accepted
time: 40ms
memory: 24228kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #14:

score: 0
Accepted
time: 48ms
memory: 22676kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #15:

score: 0
Accepted
time: 37ms
memory: 23876kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #16:

score: 0
Accepted
time: 36ms
memory: 24440kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #17:

score: 0
Accepted
time: 38ms
memory: 23600kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #18:

score: 0
Accepted
time: 48ms
memory: 24068kb

input:

1500 1500
10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #19:

score: 0
Accepted
time: 48ms
memory: 24244kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #20:

score: 0
Accepted
time: 31ms
memory: 23444kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #21:

score: 0
Accepted
time: 39ms
memory: 23260kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #22:

score: 0
Accepted
time: 44ms
memory: 24128kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #23:

score: 0
Accepted
time: 41ms
memory: 22664kb

input:

1500 1500
10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #24:

score: 0
Accepted
time: 47ms
memory: 23512kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #25:

score: 0
Accepted
time: 47ms
memory: 23208kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #26:

score: 0
Accepted
time: 30ms
memory: 24044kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #27:

score: 0
Accepted
time: 41ms
memory: 23624kb

input:

1500 1500
11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #28:

score: 0
Accepted
time: 43ms
memory: 22620kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #29:

score: 0
Accepted
time: 47ms
memory: 23780kb

input:

1500 1500
00010000000000011110111101011011110011001110011110011101111011110111000111000110001101111011110101100011011110111101000011110111101110011110000001111011110111101111011100111100110000010110101111011110110000000001100011101111011000011001111011100110001111011110011101111011110111100000011110...

output:

YES

result:

ok answer is YES

Test #30:

score: 0
Accepted
time: 37ms
memory: 23336kb

input:

1500 1500
11100111101111011110000101000011110011101111001000001101111011110111000100011110110100101000000011001110000110111101110011110111101111011110111001000011110110001111001010110000011011110110001111010010111101111011110111000000001110111101111001010111000111000000110000000011000111000001011110...

output:

YES

result:

ok answer is YES

Test #31:

score: 0
Accepted
time: 51ms
memory: 23872kb

input:

1500 1500
11110111101111011110111101111001110000000111011110111101110011100111101101011000111100000000000111101111011110000001110000010111101000011100111101101001100110001111011110100001111011110101101110011000000001110011110111101110001100111101111011110000100000011010111101111011010111101110000000...

output:

YES

result:

ok answer is YES

Test #32:

score: 0
Accepted
time: 48ms
memory: 23796kb

input:

1500 1500
11100000000000000011100000000000000000000001110000000000000000000000000000000000000000000000001110000000000000000000000000001110000000000000000000011100000000111100000011100000011100000000000000000000000000000000000000000011100000000000000000000000001111000000000000000000000000000000000000...

output:

NO

result:

ok answer is NO

Test #33:

score: 0
Accepted
time: 49ms
memory: 24436kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #34:

score: 0
Accepted
time: 32ms
memory: 23596kb

input:

1500 1500
00011100000001111000000000000011111100000000000000000000000000000000111000000011100000000001110000111111000000000000000001111000000000000000011110000000000000000000000000000000000000111111001110000000000000001111000000000000000111000000000000000000000000000000111000000000000111000000000000...

output:

YES

result:

ok answer is YES

Test #35:

score: 0
Accepted
time: 43ms
memory: 23436kb

input:

1500 1500
00000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...

output:

NO

result:

ok answer is NO

Test #36:

score: 0
Accepted
time: 39ms
memory: 23776kb

input:

1500 1500
00000000011100111100000000000000000000000000000000000000000000000000000111000000000000001110001110000000000001111111101110000000000000000000001111000000011100000000000000000000000000000000000000000011100000111000000000000000001111000000000000000000000000000000000011111000000000000000000000...

output:

NO

result:

ok answer is NO

Test #37:

score: 0
Accepted
time: 47ms
memory: 22516kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000...

output:

YES

result:

ok answer is YES

Test #38:

score: 0
Accepted
time: 44ms
memory: 23348kb

input:

1500 1500
00001110000000000000000011100000000000000000000000000000000111100000000000001111000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000111000000000000000000000011100000000011100000000000000001110000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #39:

score: 0
Accepted
time: 42ms
memory: 22556kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

NO

result:

ok answer is NO

Test #40:

score: 0
Accepted
time: 50ms
memory: 23264kb

input:

1500 1500
00000000000000011100000000000000000000000000000000000000011100000011100000000000000011100011100000000000000000000000000000000000000000000000000000111000000001111000000000000000000000000000001111000001110000000000000000001110000000000000000000000000000000000000001111011100011100000000000000...

output:

NO

result:

ok answer is NO

Test #41:

score: 0
Accepted
time: 47ms
memory: 23520kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #42:

score: 0
Accepted
time: 50ms
memory: 23548kb

input:

1500 1500
00011100000001111111000001111111000011110000000111000000000000011100000000111000000000000000001111000000000000000000000000000000011111000011110000000000000111100000000000001110000000011100001111000000001111000000000001111011110000000000000000000000000000011110000000000000000000000001110000...

output:

YES

result:

ok answer is YES

Test #43:

score: 0
Accepted
time: 44ms
memory: 23564kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

NO

result:

ok answer is NO

Test #44:

score: 0
Accepted
time: 48ms
memory: 22640kb

input:

1500 1500
00001110001110000011110000001111111000000000000111000001110000000000000000000000000000111000000000001110000000011111001111000000000000000000011110000000000111000000001111100000001111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...

output:

NO

result:

ok answer is NO

Test #45:

score: 0
Accepted
time: 50ms
memory: 23988kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #46:

score: 0
Accepted
time: 31ms
memory: 24372kb

input:

1500 1500
00000000000000000000000000000000000001110000000000000000000000000000001110000000000000011100000000000000000111100000000000000000001111000000011100000000000000111100000000000000001110000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #47:

score: 0
Accepted
time: 50ms
memory: 22520kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000001110000000000001110000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100...

output:

NO

result:

ok answer is NO

Test #48:

score: 0
Accepted
time: 30ms
memory: 23280kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #49:

score: 0
Accepted
time: 37ms
memory: 23740kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #50:

score: 0
Accepted
time: 20ms
memory: 15752kb

input:

750 1500
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #51:

score: 0
Accepted
time: 23ms
memory: 24412kb

input:

1500 750
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #52:

score: 0
Accepted
time: 19ms
memory: 14788kb

input:

750 1500
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #53:

score: 0
Accepted
time: 13ms
memory: 23736kb

input:

1500 750
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #54:

score: 0
Accepted
time: 32ms
memory: 24120kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #55:

score: 0
Accepted
time: 35ms
memory: 23728kb

input:

1500 1500
01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

YES

result:

ok answer is YES

Test #56:

score: 0
Accepted
time: 54ms
memory: 23852kb

input:

1500 1500
11111111111110110001100000101100100110111111010111111011000111100111111111101111111110011111111111110101111111111111011111111111111111111100001100000001011001011001100001111100110000000000111111111111111111111111111111111111110111111111111111111111111000111111111111000110000011111111100011...

output:

YES

result:

ok answer is YES

Test #57:

score: 0
Accepted
time: 60ms
memory: 23864kb

input:

1500 1500
01101111111000011111111111111111111110011110011101111110000111111001111111111111111111111111111101111011101101111110001101111100001111111111111111111111000001100000110111111111110011001101111111111011100001011111100111101100001111111111111111100001111111111111011111000111111111111111101110...

output:

YES

result:

ok answer is YES