QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#368927 | #6746. Merge the Rectangles | ryh7 | TL | 17ms | 25748kb | C++14 | 2.5kb | 2024-03-27 18:13:34 | 2024-03-27 18:13:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ull;
#define MAX_N 1505
string row[MAX_N], col[MAX_N];
int dpr[MAX_N][MAX_N], dpc[MAX_N][MAX_N];
int n, m;
void dfs(int tl_r, int tl_c, int br_r, int br_c) {
// cout << tl_r << " " << tl_c << " " << br_r << " " << br_c << endl;
for (int j = tl_c; j < br_c; ++j) {
if (dpc[tl_r][j] == br_r) {
for (int i = tl_r; i <= br_r; ++i) {
col[i][j] = '2';
}
dfs(tl_r, tl_c, br_r, j);
dfs(tl_r, j + 1, br_r, br_c);
}
}
for (int i = tl_r; i < br_r; ++i) {
if (dpr[i][tl_c] == br_c) {
for (int j = tl_c; j <= br_c; ++j) {
row[i][j] = '2';
}
dfs(tl_r, tl_c, i, br_c);
dfs(i + 1, tl_c, br_r, br_c);
}
}
}
bool check() {
for (int i = 0; i < n - 1; ++i) {
// cout << row[i] << endl;
for (auto c: row[i]) {
if (c == '1')return false;
}
}
for (int j = 0; j < m - 1; ++j) {
// cout << col[j] << endl;
for (auto c: col[j]) {
if (c == '1')return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n - 1; ++i) {
cin >> row[i];
dpr[i][m - 1] = (row[i][m - 1] == '1') ? m - 1 : -1;
for (int j = m - 2; j >= 0; --j) {
dpr[i][j] = (row[i][j] == '1') ? (row[i][j + 1] == '1') ? dpr[i][j + 1] : j : -1;
}
}
// for (int i = 0; i < n - 1; ++i) {
// for (int j = 0; j < m; ++j) {
// cout << dpr[i][j];
// }
// cout << endl;
// }
for (int i = 0; i < n; ++i) {
cin >> col[i];
}
for (int j = 0; j < m - 1; ++j) {
dpc[n - 1][j] = (col[n - 1][j] == '1') ? n - 1 : -1;
for (int i = n - 2; i >= 0; --i) {
dpc[i][j] = (col[i][j] == '1') ? (col[i + 1][j] == '1') ? dpc[i + 1][j] : i : -1;
}
}
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < m - 1; ++j) {
// cout << dpc[i][j];
// }
// cout << endl;
// }
dfs(0, 0, n - 1, m - 1);
if (check()) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}
//3 4
//0000
//0111
//101
//101
//110
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5808kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 5768kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 17ms
memory: 25748kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...