QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#406135#6746. Merge the RectanglesROCKETTL 37ms25412kbC++172.5kb2024-05-06 20:55:592024-05-06 20:56:01

Judging History

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

  • [2024-05-06 20:56:01]
  • 评测
  • 测评结果:TL
  • 用时:37ms
  • 内存:25412kb
  • [2024-05-06 20:55:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
#define pb push_back
// #define int ll
#define pp pop_back
#define lowbit(x) ((x) & (-x))
typedef double db ;
typedef pair<int,int> pii;
const int N = 1e6+7, M = 207, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int n, m;
string s[1507];
vector<vector<char>> a, b;
int s1[1507][1507], s2[1507][1507];

bool dfs(int x1, int y1, int x2, int y2) {
    // cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
    int f1 = 1, f = 1, f0 = 1;
    for(int i = x1; i < x2; i++) {
        // int ok1 = 0, ok2 = 0;
        // for(int j = y1; j <= y2; j++) {
        //     if(a[i][j] == 1) ok1 = true;
        //     else ok2 = true;
        // }
        if(s1[i][y2] - s1[i][y1 - 1] == y2 - y1 + 1) {
            f = f & dfs(x1, y1, i, y2);
            f = f & dfs(i + 1, y1, x2, y2);
            f0 = false;
            break;
        }
        if(s1[i][y2] - s1[i][y1 - 1] != 0) {
            f1 = false;
        }
    }
    if(f0 == 0) return f;
    for(int i = y1; i < y2; i++) {
        // int ok1 = 0, ok2 = 0;
        // for(int j = x1; j <= x2; j++) {
        //     if(b[j][i] == 1) ok1 = true;
        //     else ok2 = true;
        // }
        if(s2[x2][i] - s2[x1 - 1][i] == x2 - x1 + 1) {
            f = f & dfs(x1, y1, y1, i);
            f = f & dfs(x1, i + 1, x2, y2);
            // cout << f << endl;
            f0 = false;
            break;
        }
        if(s2[x2][i] - s2[x1 - 1][i] != 0) {
            f1 = false;
        }
    }
    if(f0 == 0) return f;
    return (f & f1);
}

void solve()
{
    cin >> n >> m;
    a = vector<vector<char>>(n + 7, vector<char>(m + 7));
    b = vector<vector<char>>(n + 7, vector<char>(m + 7));
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            s1[i][j] = s1[i][j - 1] + a[i][j] - '0';
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m - 1; j++) {
            cin >> b[i][j];
            s2[i][j] = s2[i - 1][j] + b[i][j] - '0';
        }
    }
    bool f = dfs(1, 1, n, m);
    if(f) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--){
        solve();
    }
    // cout << fixed << setprecision(10) << c << endl;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5628kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

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

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 37ms
memory: 25412kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: -100
Time Limit Exceeded

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:


result: