QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#370690 | #6746. Merge the Rectangles | hongjinjian | AC ✓ | 38ms | 21680kb | C++20 | 1.4kb | 2024-03-29 15:14:09 | 2024-03-29 15:14:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, m;
int a[1505][1505], b[1505][1505];
int dfs(int x1, int y1, int x2, int y2) {
int sum = 0;
for (int i = x1 + 1; i < x2; i++)
{
if (a[i][y2 - 1] - a[i][y1 - 1] == y2 - y1)
return dfs(x1, y1, i, y2) + dfs(i, y1, x2, y2);
sum += a[i][y2 - 1] - a[i][y1 - 1];
}
for (int j = y1 + 1; j < y2; j++)
{
if (b[x2 - 1][j] - b[x1 - 1][j] == x2 - x1)
return dfs(x1, y1, x2, j) + dfs(x1, j, x2, y2);
sum += b[x2 - 1][j] - b[x1 - 1][j];
}
return sum;
}
void solve() {
cin >> n >> m;
for (int i = 2; i <= n; i++)
{
string s;
cin >> s;
for (int j = 1; j <= m; j++)
{
a[i][j] = a[i][j - 1];
if (s[j - 1] == '1')
a[i][j]++;
}
}
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
for (int j = 2; j <= m; j++)
{
b[i][j] = b[i - 1][j];
if (s[j - 2] == '1')
b[i][j]++;
}
}
int f = dfs(1, 1, n + 1, m + 1);
if (f)
cout << "NO\n";
else
cout << "YES\n";
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int tt = 1;
while (tt--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3812kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 8ms
memory: 21468kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 20ms
memory: 21300kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 14ms
memory: 21268kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 15ms
memory: 21272kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 14ms
memory: 21448kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 8ms
memory: 21316kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #9:
score: 0
Accepted
time: 9ms
memory: 21468kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 24ms
memory: 21388kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #11:
score: 0
Accepted
time: 28ms
memory: 21604kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #12:
score: 0
Accepted
time: 19ms
memory: 21308kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #13:
score: 0
Accepted
time: 15ms
memory: 21508kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #14:
score: 0
Accepted
time: 34ms
memory: 21612kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #15:
score: 0
Accepted
time: 24ms
memory: 21680kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #16:
score: 0
Accepted
time: 17ms
memory: 21292kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #17:
score: 0
Accepted
time: 17ms
memory: 21316kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #18:
score: 0
Accepted
time: 24ms
memory: 21436kb
input:
1500 1500 10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #19:
score: 0
Accepted
time: 28ms
memory: 21428kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #20:
score: 0
Accepted
time: 14ms
memory: 21236kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #21:
score: 0
Accepted
time: 16ms
memory: 21240kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #22:
score: 0
Accepted
time: 20ms
memory: 21428kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #23:
score: 0
Accepted
time: 29ms
memory: 21384kb
input:
1500 1500 10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #24:
score: 0
Accepted
time: 26ms
memory: 21324kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #25:
score: 0
Accepted
time: 23ms
memory: 21248kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #26:
score: 0
Accepted
time: 25ms
memory: 21604kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #27:
score: 0
Accepted
time: 20ms
memory: 21480kb
input:
1500 1500 11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #28:
score: 0
Accepted
time: 17ms
memory: 21472kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #29:
score: 0
Accepted
time: 25ms
memory: 21228kb
input:
1500 1500 00010000000000011110111101011011110011001110011110011101111011110111000111000110001101111011110101100011011110111101000011110111101110011110000001111011110111101111011100111100110000010110101111011110110000000001100011101111011000011001111011100110001111011110011101111011110111100000011110...
output:
YES
result:
ok answer is YES
Test #30:
score: 0
Accepted
time: 19ms
memory: 21444kb
input:
1500 1500 11100111101111011110000101000011110011101111001000001101111011110111000100011110110100101000000011001110000110111101110011110111101111011110111001000011110110001111001010110000011011110110001111010010111101111011110111000000001110111101111001010111000111000000110000000011000111000001011110...
output:
YES
result:
ok answer is YES
Test #31:
score: 0
Accepted
time: 21ms
memory: 21468kb
input:
1500 1500 11110111101111011110111101111001110000000111011110111101110011100111101101011000111100000000000111101111011110000001110000010111101000011100111101101001100110001111011110100001111011110101101110011000000001110011110111101110001100111101111011110000100000011010111101111011010111101110000000...
output:
YES
result:
ok answer is YES
Test #32:
score: 0
Accepted
time: 29ms
memory: 21272kb
input:
1500 1500 11100000000000000011100000000000000000000001110000000000000000000000000000000000000000000000001110000000000000000000000000001110000000000000000000011100000000111100000011100000011100000000000000000000000000000000000000000011100000000000000000000000001111000000000000000000000000000000000000...
output:
NO
result:
ok answer is NO
Test #33:
score: 0
Accepted
time: 30ms
memory: 21268kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #34:
score: 0
Accepted
time: 18ms
memory: 21524kb
input:
1500 1500 00011100000001111000000000000011111100000000000000000000000000000000111000000011100000000001110000111111000000000000000001111000000000000000011110000000000000000000000000000000000000111111001110000000000000001111000000000000000111000000000000000000000000000000111000000000000111000000000000...
output:
YES
result:
ok answer is YES
Test #35:
score: 0
Accepted
time: 17ms
memory: 21252kb
input:
1500 1500 00000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...
output:
NO
result:
ok answer is NO
Test #36:
score: 0
Accepted
time: 31ms
memory: 21268kb
input:
1500 1500 00000000011100111100000000000000000000000000000000000000000000000000000111000000000000001110001110000000000001111111101110000000000000000000001111000000011100000000000000000000000000000000000000000011100000111000000000000000001111000000000000000000000000000000000011111000000000000000000000...
output:
NO
result:
ok answer is NO
Test #37:
score: 0
Accepted
time: 25ms
memory: 21264kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000...
output:
YES
result:
ok answer is YES
Test #38:
score: 0
Accepted
time: 21ms
memory: 21212kb
input:
1500 1500 00001110000000000000000011100000000000000000000000000000000111100000000000001111000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000111000000000000000000000011100000000011100000000000000001110000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #39:
score: 0
Accepted
time: 25ms
memory: 21464kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
NO
result:
ok answer is NO
Test #40:
score: 0
Accepted
time: 20ms
memory: 21212kb
input:
1500 1500 00000000000000011100000000000000000000000000000000000000011100000011100000000000000011100011100000000000000000000000000000000000000000000000000000111000000001111000000000000000000000000000001111000001110000000000000000001110000000000000000000000000000000000000001111011100011100000000000000...
output:
NO
result:
ok answer is NO
Test #41:
score: 0
Accepted
time: 24ms
memory: 21520kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #42:
score: 0
Accepted
time: 20ms
memory: 21292kb
input:
1500 1500 00011100000001111111000001111111000011110000000111000000000000011100000000111000000000000000001111000000000000000000000000000000011111000011110000000000000111100000000000001110000000011100001111000000001111000000000001111011110000000000000000000000000000011110000000000000000000000001110000...
output:
YES
result:
ok answer is YES
Test #43:
score: 0
Accepted
time: 20ms
memory: 21260kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
NO
result:
ok answer is NO
Test #44:
score: 0
Accepted
time: 24ms
memory: 21272kb
input:
1500 1500 00001110001110000011110000001111111000000000000111000001110000000000000000000000000000111000000000001110000000011111001111000000000000000000011110000000000111000000001111100000001111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...
output:
NO
result:
ok answer is NO
Test #45:
score: 0
Accepted
time: 24ms
memory: 21276kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #46:
score: 0
Accepted
time: 18ms
memory: 21444kb
input:
1500 1500 00000000000000000000000000000000000001110000000000000000000000000000001110000000000000011100000000000000000111100000000000000000001111000000011100000000000000111100000000000000001110000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #47:
score: 0
Accepted
time: 28ms
memory: 21268kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000001110000000000001110000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100...
output:
NO
result:
ok answer is NO
Test #48:
score: 0
Accepted
time: 7ms
memory: 21276kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #49:
score: 0
Accepted
time: 3ms
memory: 21268kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #50:
score: 0
Accepted
time: 12ms
memory: 12500kb
input:
750 1500 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #51:
score: 0
Accepted
time: 7ms
memory: 21268kb
input:
1500 750 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #52:
score: 0
Accepted
time: 8ms
memory: 12452kb
input:
750 1500 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #53:
score: 0
Accepted
time: 9ms
memory: 21264kb
input:
1500 750 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #54:
score: 0
Accepted
time: 18ms
memory: 21280kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #55:
score: 0
Accepted
time: 19ms
memory: 21300kb
input:
1500 1500 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
output:
YES
result:
ok answer is YES
Test #56:
score: 0
Accepted
time: 35ms
memory: 21456kb
input:
1500 1500 11111111111110110001100000101100100110111111010111111011000111100111111111101111111110011111111111110101111111111111011111111111111111111100001100000001011001011001100001111100110000000000111111111111111111111111111111111111110111111111111111111111111000111111111111000110000011111111100011...
output:
YES
result:
ok answer is YES
Test #57:
score: 0
Accepted
time: 38ms
memory: 21524kb
input:
1500 1500 01101111111000011111111111111111111110011110011101111110000111111001111111111111111111111111111101111011101101111110001101111100001111111111111111111111000001100000110111111111110011001101111111111011100001011111100111101100001111111111111111100001111111111111011111000111111111111111101110...
output:
YES
result:
ok answer is YES