QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694852#6746. Merge the RectanglesR73757565#TL 178ms21608kbC++232.4kb2024-10-31 18:48:262024-10-31 18:48:28

Judging History

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

  • [2024-10-31 18:48:28]
  • 评测
  • 测评结果:TL
  • 用时:178ms
  • 内存:21608kb
  • [2024-10-31 18:48:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
 
signed main(){
    int n, m;
    cin >> n >> m;

    vector<vector<int>> ex(n + 10, vector<int>(m + 10));
    vector<vector<int>> ey(n + 10, vector<int>(m + 10));
    
    for(int i = 1; i <= n - 1; i ++){
        for(int j = 1; j <= m; j ++){
            char c;
            cin >> c;
            ex[i][j] = (c == '1');
            ex[i][j] += ex[i - 1][j] + ex[i][j - 1] - ex[i - 1][j - 1]; 
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m - 1; j ++){
            char c;
            cin >> c;
            ey[i][j] = (c == '1');
            ey[i][j] += ey[i - 1][j] + ey[i][j - 1] - ey[i - 1][j - 1]; 
        }
    }

    auto checkx =[&](int x, int y1, int y2){
        if(y1 == y2)return true;
        int tot = ex[x][y2] - ex[x][y1] - ex[x - 1][y2] + ex[x - 1][y1];
        if(tot == abs(y1 - y2))return true;
        else return false;
    };
    auto checky =[&](int y, int x1, int x2){
        if(x1 == x2)return true;
        int tot = ey[x2][y] - ey[x1][y] - ey[x2][y - 1] + ey[x1][y - 1];
        if(tot == abs(x1 - x2))return true;
        else return false; 
    };

    // for(int i = 1; i < n; i ++){
    //     for(int j = 1; j <= m; j ++)
    //         cout << ex[i][j] << " ";
    //     cout << endl;
    // }
    // for(int i = 1; i <= n; i ++){
    //     for(int j = 1; j < m; j ++)
    //         cout << ey[i][j] << " ";
    //     cout << endl;
    // }

    function< bool(int, int, int, int)> dfs =[&] (int x1, int y1, int x2, int y2){
        // 
        if(x1 + 1 == x2 && y1 + 1 == y2)return true;
        int tx = ex[x2 - 1][y2] - ex[x1][y2] - ex[x2 - 1][y1] + ex[x1][y1];
        int ty = ey[x2][y2 - 1] - ey[x1][y2 - 1] - ey[x2][y1] + ey[x1][y1];
        if(tx == ty && tx == 0)return true;

        for(int i = x1 + 1; i <= x2 - 1; i ++){ // 
            // y1, y2 
            if(checkx(i, y1, y2)){
                if(dfs(x1, y1, i, y2) && dfs(i, y1, x2, y2))return true;
            }
        }
        for(int i = y1 + 1; i <= y2 - 1; i ++){
            // x1, x2
            if(checky(i, x1, x2)){
                if(dfs(x1, y1, x2, i) && dfs(x1, i, x2, y2))return true;
            }
        }
        return false;
    };

    if(dfs(0, 0, n, m)){
        cout << "YES" << endl;
    }else cout << "NO" << endl;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

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

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 137ms
memory: 21076kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 178ms
memory: 21608kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 135ms
memory: 21400kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 149ms
memory: 21464kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #7:

score: -100
Time Limit Exceeded

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:


result: