QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#370688 | #6746. Merge the Rectangles | hongjinjian | RE | 0ms | 0kb | C++20 | 1.7kb | 2024-03-29 15:13:20 | 2024-03-29 15:13:22 |
answer
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define lowbit(x) ((x)&-(x))
#define inf 1e9
const int N = 2e6 + 10;
const ll MOD = 1e9 + 7;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
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;
//cin >> tt;
while (tt--)
solve();
system("pause");
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
3 4 0000 0111 101 101 110