[problem:1982D]↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
// #include <atcoder/all>↵
↵
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>↵
// #define int long long↵
↵
↵
const int mod = 1e9 + 7;↵
const int N = 1e5 + 9;↵
const int inf = 1e9;↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
// using namespace atcoder;↵
↵
↵
↵
void solve() {↵
int n, m, k;↵
cin >> n >> m >> k;↵
↵
vector<vector<int>> mountain(n, vector<int>(m));↵
vector<string> mountain_type(n);↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
cin >> mountain[i][j];↵
}↵
}↵
↵
for (int i = 0; i < n; i++) {↵
cin >> mountain_type[i];↵
}↵
↵
int snowy = 0, not_snowy = 0;↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
if (mountain_type[i][j] == '0') {↵
not_snowy += mountain[i][j];↵
} else {↵
snowy += mountain[i][j];↵
}↵
}↵
}↵
↵
int diff = abs(snowy - not_snowy);↵
↵
↵
vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));↵
↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= m; j++) {↵
prefix[i][j] = (mountain_type[i - 1][j - 1] - '0') + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];↵
}↵
}↵
↵
set<int> factors;↵
↵
↵
for (int i = k; i <= n; i++) {↵
for (int j = k; j <= m; j++) {↵
int total_snowy = prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k];↵
factors.insert(abs(k * k - 2 * total_snowy));↵
}↵
}↵
↵
int tot_gcd = (factors.size()==0) ? 0 : *factors.begin();↵
if(factors.size()==0) {↵
if(diff == 0) {↵
cout << "YES" << endl;↵
} else {↵
cout << "NO" << endl;↵
}↵
return;↵
}↵
for (auto x : factors) {↵
if (x == 0) {↵
continue;↵
}↵
tot_gcd = __gcd(tot_gcd, x);↵
}↵
↵
if (diff % tot_gcd == 0) {↵
cout << "YES" << endl;↵
} else {↵
cout << "NO" << endl;↵
}↵
}↵
↵
↵
signed main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
// #include <atcoder/all>↵
↵
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>↵
// #define int long long↵
↵
↵
const int mod = 1e9 + 7;↵
const int N = 1e5 + 9;↵
const int inf = 1e9;↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
// using namespace atcoder;↵
↵
↵
↵
void solve() {↵
int n, m, k;↵
cin >> n >> m >> k;↵
↵
vector<vector<int>> mountain(n, vector<int>(m));↵
vector<string> mountain_type(n);↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
cin >> mountain[i][j];↵
}↵
}↵
↵
for (int i = 0; i < n; i++) {↵
cin >> mountain_type[i];↵
}↵
↵
int snowy = 0, not_snowy = 0;↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
if (mountain_type[i][j] == '0') {↵
not_snowy += mountain[i][j];↵
} else {↵
snowy += mountain[i][j];↵
}↵
}↵
}↵
↵
int diff = abs(snowy - not_snowy);↵
↵
↵
vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));↵
↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= m; j++) {↵
prefix[i][j] = (mountain_type[i - 1][j - 1] - '0') + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];↵
}↵
}↵
↵
set<int> factors;↵
↵
↵
for (int i = k; i <= n; i++) {↵
for (int j = k; j <= m; j++) {↵
int total_snowy = prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k];↵
factors.insert(abs(k * k - 2 * total_snowy));↵
}↵
}↵
↵
int tot_gcd = (factors.size()==0) ? 0 : *factors.begin();↵
if(factors.size()==0) {↵
if(diff == 0) {↵
cout << "YES" << endl;↵
} else {↵
cout << "NO" << endl;↵
}↵
return;↵
}↵
for (auto x : factors) {↵
if (x == 0) {↵
continue;↵
}↵
tot_gcd = __gcd(tot_gcd, x);↵
}↵
↵
if (diff % tot_gcd == 0) {↵
cout << "YES" << endl;↵
} else {↵
cout << "NO" << endl;↵
}↵
}↵
↵
↵
signed main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
