QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#396293#6746. Merge the RectanglesqilingWA 8ms25812kbC++232.0kb2024-04-22 17:04:122024-04-22 17:04:13

Judging History

你现在查看的是最新测评结果

  • [2024-04-22 17:04:13]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:25812kb
  • [2024-04-22 17:04:12]
  • 提交

answer

#include <bits/stdc++.h>

#define mod 998244353
#define eps 1e-5
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
//#define int long long

using namespace std;
using i64 = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> h(n + 5), l(n + 5);
    for (int i = 2; i <= n; ++ i) {
        cin >> h[i];
        h[i] = ' ' + h[i];
    }
    for (int i = 1; i <= n; ++ i) {
        cin >> l[i];
        l[i] = ' ' + l[i];
    }
    vector<vector<int>> rsum(n + 5, vector<int> (m + 5, 0)), csum(n + 5, vector<int> (m + 5, 0));
    for (int i = 2; i <= n; ++ i) {
        for (int j = 2; j <= m + 1; ++ j) {
            rsum[i][j] = rsum[i][j - 1] + (h[i][j - 1] == '1');
        }
    }
    for (int i = 2; i <= m; ++ i) {
        for (int j = 2; j <= n + 1; ++ j) {
            csum[i][j] = csum[i][j - 1] + (l[j - 1][i - 1] == '1');
        }
    }
    
    function<bool(int, int, int, int)> dfs = [&](int x1, int y1, int x2, int y2) {
        bool f = true;
        for (int i = x1 + 1; i < x2; ++ i) {
            if(rsum[i][y2] - rsum[i][y1 - 1]) f =false;
            if(rsum[i][y2] - rsum[i][y1 - 1] == y2 - y1) {
//                if(dfs(x1, y1, i, y2)) {
//                    return dfs(i, y1, x2, y2);
//                }
                return dfs(x1, y1, i, y2) && dfs(i, y1, x2, y2);
            }
        }
        for (int i = y1 + 1; i < y2; ++ i) {
            if(csum[i][x2] - csum[i][x1 - 1]) f = false;
            if(csum[i][x2] - csum[i][x1 - 1] == x2 - x1) {
//                if(dfs(x1, y1, x2, i)) {
//                    return dfs(x1, i, x2, y2);
//                };
                return dfs(x1, y1, x2, i) && dfs(x1, i, x2, y2);
            }
        }
        return f;
    };
    if(dfs(1, 1, n + 1, m + 1)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
//    cin >> t;
    while(t --)
        solve();
    return 0;
}
/*
 3 4
 0000
 0111
 101
 101
 110
 */
/*
 3 3
 110
 011
 01
 11
 10
 */

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 8ms
memory: 25612kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: -100
Wrong Answer
time: 8ms
memory: 25812kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

wrong answer expected YES, found NO