QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369019#6746. Merge the Rectanglesryh7TL 15ms25800kbC++142.5kb2024-03-27 19:31:252024-03-27 19:31:25

Judging History

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

  • [2024-03-27 19:31:25]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:25800kb
  • [2024-03-27 19:31:25]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ull;

#define MAX_N 1505
string row[MAX_N], col[MAX_N];
int dpr[MAX_N][MAX_N], dpc[MAX_N][MAX_N];
int n, m;

void dfs(int tl_r, int tl_c, int br_r, int br_c) {
//    cout << tl_r << " " << tl_c << " " << br_r << " " << br_c << endl;
    for (int j = tl_c; j < br_c; ++j) {
        if (dpc[tl_r][j] == br_r) {
            for (int i = tl_r; i <= br_r; ++i) {
                col[i][j] = '2';
            }
            dfs(tl_r, tl_c, br_r, j);
            dfs(tl_r, j + 1, br_r, br_c);
return;
        }
    }
    for (int i = tl_r; i < br_r; ++i) {
        if (dpr[i][tl_c] == br_c) {
            for (int j = tl_c; j <= br_c; ++j) {
                row[i][j] = '2';
            }
            dfs(tl_r, tl_c, i, br_c);
            dfs(i + 1, tl_c, br_r, br_c);
        }
    }
}

bool check() {
    for (int i = 0; i < n - 1; ++i) {
//        cout << row[i] << endl;
        for (auto c: row[i]) {
            if (c == '1')return false;
        }
    }
    for (int j = 0; j < m - 1; ++j) {
//        cout << col[j] << endl;
        for (auto c: col[j]) {
            if (c == '1')return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
        cin >> row[i];
        dpr[i][m - 1] = (row[i][m - 1] == '1') ? m - 1 : -1;
        for (int j = m - 2; j >= 0; --j) {
            dpr[i][j] = (row[i][j] == '1') ? (row[i][j + 1] == '1') ? dpr[i][j + 1] : j : -1;
        }
    }
//    for (int i = 0; i < n - 1; ++i) {
//        for (int j = 0; j < m; ++j) {
//            cout << dpr[i][j];
//        }
//        cout << endl;
//    }
    for (int i = 0; i < n; ++i) {
        cin >> col[i];
    }
    for (int j = 0; j < m - 1; ++j) {
        dpc[n - 1][j] = (col[n - 1][j] == '1') ? n - 1 : -1;
        for (int i = n - 2; i >= 0; --i) {
            dpc[i][j] = (col[i][j] == '1') ? (col[i + 1][j] == '1') ? dpc[i + 1][j] : i : -1;
        }
    }
//    for (int i = 0; i < n; ++i) {
//        for (int j = 0; j < m - 1; ++j) {
//            cout << dpc[i][j];
//        }
//        cout << endl;
//    }
    dfs(0, 0, n - 1, m - 1);
    if (check()) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}
//3 4
//0000
//0111
//101
//101
//110

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 5784kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 15ms
memory: 25800kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: -100
Time Limit Exceeded

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:


result: