QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#370672#6746. Merge the RectanglesL_M_YAC ✓45ms51056kbC++141.8kb2024-03-29 14:53:092024-03-29 14:53:10

Judging History

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

  • [2024-03-29 14:53:10]
  • 评测
  • 测评结果:AC
  • 用时:45ms
  • 内存:51056kb
  • [2024-03-29 14:53:09]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define lowbit(x) ((x)&-(x))
#define inf 99999999
const int N = 2e3 + 5;
const int MOD = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
int n, m, a[N][N], b[N][N], sumr[N][N] = { 0 }, sumc[N][N] = { 0 };
bool dfs(int x1, int y1, int x2, int y2)
{
	int sum = 0;
	for (int i = y1 + 1; i < y2; i++)
	{
		if (sumc[i][x2 - 1] - sumc[i][x1 - 1] == x2 - x1)
		{
			return (dfs(x1, y1, x2, i) && dfs(x1, i, x2, y2));
		}
		sum += sumc[i][x2 - 1] - sumc[i][x1 - 1];
	}
	for (int i = x1 + 1; i < x2; i++)
	{
		if (sumr[i][y2 - 1] - sumr[i][y1 - 1] == y2 - y1)
		{
			return (dfs(x1, y1, i, y2) && dfs(i, y1, x2, y2));
		}
		sum += sumr[i][y2 - 1] - sumr[i][y1 - 1];
	}
	if (sum == 0)
		return true;
	return false;
}
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		a[1][i] = a[n + 1][i] = 1;
	for (int i = 1; i <= n; i++)
		b[1][i] = b[m + 1][i] = 1;
	for (int i = 2; i <= n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)
			a[i][j + 1] = s[j] - '0';
	}
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)
			b[j + 2][i] = s[j] - '0';
	}
	for (int i = 1; i <= n + 1; i++)
		for (int j = 1; j <= m; j++)
			sumr[i][j] = sumr[i][j - 1] + a[i][j];
	for (int i = 1; i <= m + 1; i++)
		for (int j = 1; j <= n; j++)
			sumc[i][j] = sumc[i][j - 1] + b[i][j];
	if (dfs(1, 1, n + 1, m + 1))
		cout << "YES\n";
	else
		cout << "NO\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--)
	{
		solve();
		cout << "\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 4
0000
0111
101
101
110

output:

YES


result:

ok answer is YES

Test #2:

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

input:

3 3
110
011
01
11
10

output:

NO


result:

ok answer is NO

Test #3:

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

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #4:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #5:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #6:

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

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #7:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #8:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #9:

score: 0
Accepted
time: 16ms
memory: 50868kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #10:

score: 0
Accepted
time: 27ms
memory: 50656kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #11:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #12:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #13:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #14:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #15:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #16:

score: 0
Accepted
time: 33ms
memory: 50664kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #17:

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

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #18:

score: 0
Accepted
time: 45ms
memory: 50764kb

input:

1500 1500
10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #19:

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

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #20:

score: 0
Accepted
time: 16ms
memory: 50700kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #21:

score: 0
Accepted
time: 16ms
memory: 50676kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #22:

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

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #23:

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

input:

1500 1500
10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #24:

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

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #25:

score: 0
Accepted
time: 15ms
memory: 50632kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #26:

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

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #27:

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

input:

1500 1500
11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #28:

score: 0
Accepted
time: 8ms
memory: 50632kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #29:

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

input:

1500 1500
00010000000000011110111101011011110011001110011110011101111011110111000111000110001101111011110101100011011110111101000011110111101110011110000001111011110111101111011100111100110000010110101111011110110000000001100011101111011000011001111011100110001111011110011101111011110111100000011110...

output:

YES


result:

ok answer is YES

Test #30:

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

input:

1500 1500
11100111101111011110000101000011110011101111001000001101111011110111000100011110110100101000000011001110000110111101110011110111101111011110111001000011110110001111001010110000011011110110001111010010111101111011110111000000001110111101111001010111000111000000110000000011000111000001011110...

output:

YES


result:

ok answer is YES

Test #31:

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

input:

1500 1500
11110111101111011110111101111001110000000111011110111101110011100111101101011000111100000000000111101111011110000001110000010111101000011100111101101001100110001111011110100001111011110101101110011000000001110011110111101110001100111101111011110000100000011010111101111011010111101110000000...

output:

YES


result:

ok answer is YES

Test #32:

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

input:

1500 1500
11100000000000000011100000000000000000000001110000000000000000000000000000000000000000000000001110000000000000000000000000001110000000000000000000011100000000111100000011100000011100000000000000000000000000000000000000000011100000000000000000000000001111000000000000000000000000000000000000...

output:

NO


result:

ok answer is NO

Test #33:

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

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #34:

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

input:

1500 1500
00011100000001111000000000000011111100000000000000000000000000000000111000000011100000000001110000111111000000000000000001111000000000000000011110000000000000000000000000000000000000111111001110000000000000001111000000000000000111000000000000000000000000000000111000000000000111000000000000...

output:

YES


result:

ok answer is YES

Test #35:

score: 0
Accepted
time: 3ms
memory: 50612kb

input:

1500 1500
00000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...

output:

NO


result:

ok answer is NO

Test #36:

score: 0
Accepted
time: 22ms
memory: 50632kb

input:

1500 1500
00000000011100111100000000000000000000000000000000000000000000000000000111000000000000001110001110000000000001111111101110000000000000000000001111000000011100000000000000000000000000000000000000000011100000111000000000000000001111000000000000000000000000000000000011111000000000000000000000...

output:

NO


result:

ok answer is NO

Test #37:

score: 0
Accepted
time: 16ms
memory: 50848kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000...

output:

YES


result:

ok answer is YES

Test #38:

score: 0
Accepted
time: 15ms
memory: 50624kb

input:

1500 1500
00001110000000000000000011100000000000000000000000000000000111100000000000001111000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000111000000000000000000000011100000000011100000000000000001110000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #39:

score: 0
Accepted
time: 16ms
memory: 50668kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

NO


result:

ok answer is NO

Test #40:

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

input:

1500 1500
00000000000000011100000000000000000000000000000000000000011100000011100000000000000011100011100000000000000000000000000000000000000000000000000000111000000001111000000000000000000000000000001111000001110000000000000000001110000000000000000000000000000000000000001111011100011100000000000000...

output:

NO


result:

ok answer is NO

Test #41:

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

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #42:

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

input:

1500 1500
00011100000001111111000001111111000011110000000111000000000000011100000000111000000000000000001111000000000000000000000000000000011111000011110000000000000111100000000000001110000000011100001111000000001111000000000001111011110000000000000000000000000000011110000000000000000000000001110000...

output:

YES


result:

ok answer is YES

Test #43:

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

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

NO


result:

ok answer is NO

Test #44:

score: 0
Accepted
time: 16ms
memory: 50672kb

input:

1500 1500
00001110001110000011110000001111111000000000000111000001110000000000000000000000000000111000000000001110000000011111001111000000000000000000011110000000000111000000001111100000001111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...

output:

NO


result:

ok answer is NO

Test #45:

score: 0
Accepted
time: 18ms
memory: 50844kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #46:

score: 0
Accepted
time: 29ms
memory: 50852kb

input:

1500 1500
00000000000000000000000000000000000001110000000000000000000000000000001110000000000000011100000000000000000111100000000000000000001111000000011100000000000000111100000000000000001110000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #47:

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

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000001110000000000001110000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100...

output:

NO


result:

ok answer is NO

Test #48:

score: 0
Accepted
time: 12ms
memory: 50668kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #49:

score: 0
Accepted
time: 15ms
memory: 50680kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES


result:

ok answer is YES

Test #50:

score: 0
Accepted
time: 16ms
memory: 36144kb

input:

750 1500
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #51:

score: 0
Accepted
time: 12ms
memory: 36372kb

input:

1500 750
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO


result:

ok answer is NO

Test #52:

score: 0
Accepted
time: 11ms
memory: 36196kb

input:

750 1500
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #53:

score: 0
Accepted
time: 8ms
memory: 36220kb

input:

1500 750
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #54:

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

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES


result:

ok answer is YES

Test #55:

score: 0
Accepted
time: 27ms
memory: 50612kb

input:

1500 1500
01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

YES


result:

ok answer is YES

Test #56:

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

input:

1500 1500
11111111111110110001100000101100100110111111010111111011000111100111111111101111111110011111111111110101111111111111011111111111111111111100001100000001011001011001100001111100110000000000111111111111111111111111111111111111110111111111111111111111111000111111111111000110000011111111100011...

output:

YES


result:

ok answer is YES

Test #57:

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

input:

1500 1500
01101111111000011111111111111111111110011110011101111110000111111001111111111111111111111111111101111011101101111110001101111100001111111111111111111111000001100000110111111111110011001101111111111011100001011111100111101100001111111111111111100001111111111111011111000111111111111111101110...

output:

YES


result:

ok answer is YES