QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387575 | #6746. Merge the Rectangles | k1nsom | TL | 154ms | 76736kb | C++17 | 2.2kb | 2024-04-12 16:52:30 | 2024-04-12 16:52:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 1510
#define endl '\n'
int n, m, cnt = 0, a[N][N], b[N][N], l[N][N] = {0}, r[N][N] = {0};
bool vis[N][N] = {0};
char c;
struct rectangle
{
int sx, sy, tx, ty;
};
vector<rectangle> v;
void dfs(int sx, int sy, int tx, int ty)
{
for (int i = sx; i < tx; i++)
if (l[i][ty] - l[i][sy - 1] == ty - sy + 1)
{
cnt++;
dfs(sx, sy, i, ty);
dfs(i + 1, sy, tx, ty);
}
for (int i = sy; i < ty; i++)
if (r[tx][i] - r[sx - 1][i] == tx - sx + 1)
{
cnt++;
dfs(sx, sy, tx, i);
dfs(sx, i + 1, tx, ty);
}
}
signed main()
{
cin >> n >> m;
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
{
cin >> c;
a[i][j] = c - '0';
l[i][j] = l[i][j - 1] + a[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++)
{
cin >> c;
b[i][j] = c - '0';
r[i][j] = r[i - 1][j] + b[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!vis[i][j])
{
int sx = i, tx = i, sy = j, ty = j;
while (!a[tx][sy])
{
tx++;
if (tx > n)
{
tx--;
break;
}
}
while (!b[sx][ty])
{
ty++;
if (ty > m)
{
ty--;
break;
}
}
for (int t = sx; t <= tx; t++)
for (int k = sy; k <= ty; k++)
vis[t][k] = 1;
v.push_back({sx, sy, tx, ty});
}
// for (auto u : v)
//{
// cout << u.sx << ' ' << u.sy << ' ' << u.tx << ' ' << u.ty << endl;
// }
dfs(1, 1, n, m);
if (cnt + 1 == v.size())
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5724kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 154ms
memory: 76736kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...