QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#695005 | #6746. Merge the Rectangles | R73757565# | TL | 65ms | 22028kb | C++20 | 2.1kb | 2024-10-31 19:06:57 | 2024-10-31 19:06:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// typedef pair<int, int> PII;
// typedef long long LL;
const int N = 1510;
vector<vector<int>> ex(N + 10, vector<int>(N + 10, 0));
vector<vector<int>> ey(N + 10, vector<int>(N + 10, 0));
int n, m;
bool checkx (int x, int y1, int y2){
if(y1 == y2)return true;
int tot = ex[x][y2] - ex[x][y1] - ex[x - 1][y2] + ex[x - 1][y1];
if(tot == abs(y1 - y2))return true;
else return false;
}
bool checky (int y, int x1, int x2){
if(x1 == x2)return true;
int tot = ey[x2][y] - ey[x1][y] - ey[x2][y - 1] + ey[x1][y - 1];
if(tot == abs(x1 - x2))return true;
else return false;
}
bool dfs (int x1, int y1, int x2, int y2){
if(x1 + 1 == x2 && y1 + 1 == y2)return true;
int tx = ex[x2 - 1][y2] - ex[x1][y2] - ex[x2 - 1][y1] + ex[x1][y1];
int ty = ey[x2][y2 - 1] - ey[x1][y2 - 1] - ey[x2][y1] + ey[x1][y1];
if(tx == ty && tx == 0)return true;
for(int i = x1 + 1; i <= x2 - 1; i ++){ //
// y1, y2
if(checkx(i, y1, y2)){
if(dfs(x1, y1, i, y2) && dfs(i, y1, x2, y2))return true;
}
}
for(int i = y1 + 1; i <= y2 - 1; i ++){
// x1, x2
if(checky(i, x1, x2)){
if(dfs(x1, y1, x2, i) && dfs(x1, i, x2, y2))return true;
}
}
return false;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n - 1; i ++){
for(int j = 1; j <= m; j ++){
char c;
cin >> c;
ex[i][j] = (c == '1');
ex[i][j] += ex[i - 1][j] + ex[i][j - 1] - ex[i - 1][j - 1];
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m - 1; j ++){
char c;
cin >> c;
ey[i][j] = (c == '1');
ey[i][j] += ey[i - 1][j] + ey[i][j - 1] - ey[i - 1][j - 1];
}
}
if(dfs(0, 0, n, m)){
cout << "YES" << '\n';
}else cout << "NO" << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22028kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 3ms
memory: 21788kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 37ms
memory: 22020kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 65ms
memory: 21868kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 32ms
memory: 21800kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 44ms
memory: 21768kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...