Submission #66777599

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define pb push_back

void solve() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> field(h);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            char c;
            cin >> c;
            field[i].push_back(c);
        }
    }
    if (h > w) {
        vector<vector<char>> newfield(w);
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                newfield[i].push_back(field[j][i]);
            }
        }
        field = newfield;
        swap(h, w);
    }

    int sum[h + 1][w + 1];
    for (int i = 0; i <= h; i++) {
        sum[i][0] = 0;
    }
    for (int j = 0; j <= w; j++) {
        sum[0][j] = 0;
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (field[i][j] == '#') {
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + 1;
            } else {
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] - 1;
            }
        }
    }

    ll ans = 0;
    vector<int> mp(2 * h * w + 30);
    for (int i = 0; i < 2 * h * w + 30; i++) {
        mp[i] = 0;
    }
    for (int i = 0; i <= h; i++) {
        for (int j = i + 1; j <= h; j++) {
            for (int k = 0; k <= w; k++) {
                mp[sum[j][k] - sum[i][k] + (h * w + 10)]++;
                ans += mp[sum[j][k] - sum[i][k] + (h * w + 10)] - 1;
            }
            for (int k = 0; k <= w; k++) {
                mp[sum[j][k] - sum[i][k] + (h * w + 10)]--;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    for (int _ = 0; _ < T; _++) {
        solve();
    }
}

Submission Info

Submission Time
Task F - Balanced Rectangles
User CheckMate
Language C++ 20 (gcc 12.2)
Score 525
Code Size 1867 Byte
Status AC
Exec Time 269 ms
Memory 22312 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 525 / 525
Status
AC × 1
AC × 43
Set Name Test Cases
Sample sample_01.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt
Case Name Status Exec Time Memory
hand_01.txt AC 32 ms 22312 KiB
hand_02.txt AC 14 ms 8124 KiB
hand_03.txt AC 33 ms 22164 KiB
hand_04.txt AC 15 ms 8244 KiB
sample_01.txt AC 1 ms 3616 KiB
test_01.txt AC 1 ms 3584 KiB
test_02.txt AC 1 ms 3536 KiB
test_03.txt AC 1 ms 3376 KiB
test_04.txt AC 1 ms 3636 KiB
test_05.txt AC 1 ms 3492 KiB
test_06.txt AC 2 ms 3456 KiB
test_07.txt AC 2 ms 3428 KiB
test_08.txt AC 3 ms 3480 KiB
test_09.txt AC 4 ms 3484 KiB
test_10.txt AC 9 ms 3552 KiB
test_11.txt AC 9 ms 3484 KiB
test_12.txt AC 53 ms 3492 KiB
test_13.txt AC 37 ms 3536 KiB
test_14.txt AC 14 ms 7568 KiB
test_15.txt AC 25 ms 13464 KiB
test_16.txt AC 153 ms 7136 KiB
test_17.txt AC 133 ms 7724 KiB
test_18.txt AC 154 ms 7552 KiB
test_19.txt AC 131 ms 7136 KiB
test_20.txt AC 55 ms 3492 KiB
test_21.txt AC 148 ms 7196 KiB
test_22.txt AC 124 ms 6552 KiB
test_23.txt AC 149 ms 7452 KiB
test_24.txt AC 161 ms 7052 KiB
test_25.txt AC 96 ms 5608 KiB
test_26.txt AC 65 ms 4252 KiB
test_27.txt AC 71 ms 7080 KiB
test_28.txt AC 42 ms 5428 KiB
test_29.txt AC 64 ms 5516 KiB
test_30.txt AC 86 ms 7112 KiB
test_31.txt AC 111 ms 6764 KiB
test_32.txt AC 65 ms 5172 KiB
test_33.txt AC 269 ms 7192 KiB
test_34.txt AC 214 ms 7592 KiB
test_35.txt AC 242 ms 7120 KiB
test_36.txt AC 161 ms 7572 KiB
test_37.txt AC 194 ms 7092 KiB
test_38.txt AC 70 ms 8084 KiB