QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373376#6746. Merge the Rectanglesteam129TL 1481ms197472kbC++142.4kb2024-04-01 15:35:112024-04-01 15:35:12

Judging History

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

  • [2024-04-01 15:35:12]
  • 评测
  • 测评结果:TL
  • 用时:1481ms
  • 内存:197472kb
  • [2024-04-01 15:35:11]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<map>
#include<string>
#include<iomanip>
#include<climits>
#include <sstream>
#include<functional>
#include <unordered_map>
#include<array>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
ll t, n, k, a, b,m;
char c;
const ll N = 1.5e3+10;
const ll MOD = 998244353;
const int B = 0, T = 3, L = 2, R = 1;
int arr[N][N][4],pres[N][N][2];
set<pair<pii, pii>> recs;
bool TL(pii dot) {
	return arr[dot.first][dot.second][T] == 1 && arr[dot.first][dot.second][L] == 1;
}
int al1 = 1;
void ini() {
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c;
			a = c - 48;
			if (a != 1)
				al1 = 0;
			if (a) {
				arr[i][j][B] = arr[i + 1][j][T] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m - 1; j++) {
			cin >> c;
			a = c - 48;
			if (a != 1)
				al1 = 0;
			if (a) {
				arr[i][j][R] = arr[i][j + 1][L] = 1;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		arr[0][i][T] = arr[n - 1][i][B] = 1;
	}
	for (int i = 0; i < n; i++) {
		arr[i][0][L] = arr[i][m - 1][R] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (TL({ i,j })) {
				int r = j, b = i;
				while (!arr[i][r][R])
					r++;
				while (!arr[b][j][B])
					b++;
				recs.insert({ {i,j},{b,r} });
			}
		}
	}
	for (int j = m - 2; j >= 0; j--) {
		for (int i = n - 1; i >= 0; i--) {
			if(arr[i][j][R] == 1)
				pres[i][j][R] = pres[i + 1][j][R] + arr[i][j][R];
		}
	}
	for (int i = n - 2; i >= 0; i--)
		for (int j = m - 1; j >= 0; j--) {
			if (arr[i][j][B] == 1)
				pres[i][j][B] = pres[i][j + 1][B] + arr[i][j][B];
		}
}
int f = 1;
bool solve(pii tl, pii br) {
	if (f == 0)
		return 0;
	if (recs.count({ tl,br }))
		return 1;
	int t = tl.first, b = br.first, l = tl.second, r = br.second;
	for (int i = l; i < r; i++) {
		if (pres[t][i][R] >= (int)abs(b - t) + 1) {
			return solve(tl, { b,i }) && solve({ t,i + 1 }, br);
		}
	}
	for (int i = t; i < b; i++) {
		if (pres[i][l][B] >= (int)abs(r - l) + 1) {
			return solve(tl, { i,r }) && solve({ i + 1,l }, br);
		}
	}
	f = 0;
	return 0;
}
int main()
{
	cin >> n >> m;
	ini();
	if (al1) {
		cout << "YES";
	}
	else
	cout << ((solve({ 0,0 }, { n - 1,m - 1 }) == 1) ? "YES" : "NO");
}

详细

Test #1:

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

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

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

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 140ms
memory: 38600kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 701ms
memory: 197380kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 145ms
memory: 57008kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 149ms
memory: 56964kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #7:

score: 0
Accepted
time: 1481ms
memory: 197472kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #8:

score: 0
Accepted
time: 698ms
memory: 197300kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #9:

score: 0
Accepted
time: 681ms
memory: 197136kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #10:

score: -100
Time Limit Exceeded

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:


result: