Submission #66773845

---

Source Code Expand

// Original Python Code:
/*
import os
import sys

import numpy as np


def solve(h, w, field):
    if h > w:
        h, w = w, h
        field = field.T

    acc = np.zeros((h + 1, w + 1), dtype=np.int64)
    for i in range(h):
        for j in range(w):
            acc[i + 1, j + 1] = acc[i + 1, j] + field[i, j]
    for j in range(w):
        for i in range(h):
            acc[i + 1, j + 1] += acc[i, j + 1]
    ans = 0
    for i1 in range(h):
        for i2 in range(i1 + 1, h + 1):
            cnt = {}
            for j in range(w + 1):
                d = acc[i1, j] - acc[i2, j]
                if d in cnt:
                    cnt[d] += 1
                else:
                    cnt[d] = 1
            for c in cnt.values():
                ans += c * (c - 1) // 2
    return ans


t = int(input())
for _ in range(t):
    h, w = map(int, input().split())
    field = []
    getter = lambda c: '._#'.index(c) - 1
    for _ in range(h):
        field.append(list(map(getter, input())))
    field = np.array(field, dtype=np.int64)
    ans = solve(h, w, field)
    print(ans)
*/

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

int getter(char c) {
    if (c == '.') return -1;
    if (c == '_') return 0;
    if (c == '#') return 1;
    return 0; // should not happen
}

ll solve(int h, int w, vector<vector<int>> field) {
    if (h > w) {
        swap(h, w);
        vector<vector<int>> new_field(w, vector<int>(h));
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                new_field[j][i] = field[i][j];
        field = new_field;
    }

    vector<vector<ll>> acc(h + 1, vector<ll>(w + 1, 0));
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            acc[i + 1][j + 1] = acc[i + 1][j] + field[i][j];

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

    ll ans = 0;
    for (int i1 = 0; i1 < h; ++i1) {
        for (int i2 = i1 + 1; i2 <= h; ++i2) {
            unordered_map<ll, int> cnt;
            for (int j = 0; j <= w; ++j) {
                ll d = acc[i1][j] - acc[i2][j];
                cnt[d]++;
            }
            for (auto& [key, c] : cnt) {
                ans += 1LL * c * (c - 1) / 2;
            }
        }
    }
    return ans;
}

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

    int t;
    cin >> t;
    while (t--) {
        int h, w;
        cin >> h >> w;
        vector<vector<int>> field(h, vector<int>(w));
        for (int i = 0; i < h; ++i) {
            string line;
            cin >> line;
            for (int j = 0; j < w; ++j) {
                field[i][j] = getter(line[j]);
            }
        }
        cout << solve(h, w, field) << '\n';
    }

    return 0;
}

Submission Info

Judge Result