QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#396293 | #6746. Merge the Rectangles | qiling | WA | 8ms | 25812kb | C++23 | 2.0kb | 2024-04-22 17:04:12 | 2024-04-22 17:04:13 |
Judging History
answer
#include <bits/stdc++.h>
#define mod 998244353
#define eps 1e-5
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
//#define int long long
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<string> h(n + 5), l(n + 5);
for (int i = 2; i <= n; ++ i) {
cin >> h[i];
h[i] = ' ' + h[i];
}
for (int i = 1; i <= n; ++ i) {
cin >> l[i];
l[i] = ' ' + l[i];
}
vector<vector<int>> rsum(n + 5, vector<int> (m + 5, 0)), csum(n + 5, vector<int> (m + 5, 0));
for (int i = 2; i <= n; ++ i) {
for (int j = 2; j <= m + 1; ++ j) {
rsum[i][j] = rsum[i][j - 1] + (h[i][j - 1] == '1');
}
}
for (int i = 2; i <= m; ++ i) {
for (int j = 2; j <= n + 1; ++ j) {
csum[i][j] = csum[i][j - 1] + (l[j - 1][i - 1] == '1');
}
}
function<bool(int, int, int, int)> dfs = [&](int x1, int y1, int x2, int y2) {
bool f = true;
for (int i = x1 + 1; i < x2; ++ i) {
if(rsum[i][y2] - rsum[i][y1 - 1]) f =false;
if(rsum[i][y2] - rsum[i][y1 - 1] == y2 - y1) {
// if(dfs(x1, y1, i, y2)) {
// return dfs(i, y1, x2, y2);
// }
return dfs(x1, y1, i, y2) && dfs(i, y1, x2, y2);
}
}
for (int i = y1 + 1; i < y2; ++ i) {
if(csum[i][x2] - csum[i][x1 - 1]) f = false;
if(csum[i][x2] - csum[i][x1 - 1] == x2 - x1) {
// if(dfs(x1, y1, x2, i)) {
// return dfs(x1, i, x2, y2);
// };
return dfs(x1, y1, x2, i) && dfs(x1, i, x2, y2);
}
}
return f;
};
if(dfs(1, 1, n + 1, m + 1)) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t --)
solve();
return 0;
}
/*
3 4
0000
0111
101
101
110
*/
/*
3 3
110
011
01
11
10
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 8ms
memory: 25612kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: -100
Wrong Answer
time: 8ms
memory: 25812kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
wrong answer expected YES, found NO