Submission #76484452

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, K;
    cin >> H >> W >> K;
    vector<string> grid(H);
    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
    }

    // 转置，让行数较小
    if (H > W) {
        vector<string> new_grid(W, string(H, '0'));
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                new_grid[j][i] = grid[i][j];
            }
        }
        grid = move(new_grid);
        swap(H, W);
    }

    const int max_sum = H * W;          // 前缀和的最大可能值
    vector<int> cnt(max_sum + 1, 0);    // 计数数组
    vector<int> used(max_sum + 1, 0);   // 时间戳数组
    long long ans = 0;
    int cur_stamp = 0;

    for (int top = 0; top < H; ++top) {
        vector<int> col_sum(W, 0);      // 列和，从 top 行到底部行累加
        for (int bottom = top; bottom < H; ++bottom) {
            // 更新列和
            for (int j = 0; j < W; ++j) {
                col_sum[j] += (grid[bottom][j] == '1');
            }

            // 统计 col_sum 中连续子数组和为 K 的个数
            ++cur_stamp;
            int prefix = 0;
            used[0] = cur_stamp;
            cnt[0] = 1;
            for (int j = 0; j < W; ++j) {
                prefix += col_sum[j];
                int need = prefix - K;
                if (need >= 0 && need <= max_sum && used[need] == cur_stamp) {
                    ans += cnt[need];
                }
                if (used[prefix] != cur_stamp) {
                    used[prefix] = cur_stamp;
                    cnt[prefix] = 0;
                }
                cnt[prefix]++;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result