Submission #76477924

Source Code Expand

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

const int N = 510;
const int MAXK = 250005;

int n, m, k;
int sum[N][N];
int cnt[MAXK];
string s;

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

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= m; j++) {
            int v = s[j - 1] - '0';
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1]
                      - sum[i - 1][j - 1] + v;
        }
    }

    long long ans = 0;
    for (int r1 = 1; r1 <= n; r1++) {
        for (int r2 = r1; r2 <= n; r2++) {

            fill(cnt, cnt + MAXK, 0);
            cnt[0] = 1;

            for (int c = 1; c <= m; c++) {
                int cur = sum[r2][c] - sum[r1 - 1][c];
                if (cur >= k) ans += cnt[cur - k];
                cnt[cur]++;
            }
        }
    }

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

Submission Info

Submission Time
Task D - Count Subgrid Sum = K
User Axiom_
Language C++23 (GCC 15.2.0)
Score 425
Code Size 943 Byte
Status AC
Exec Time 2146 ms
Memory 5580 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 31
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.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
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 4440 KiB
sample_02.txt AC 1 ms 4500 KiB
sample_03.txt AC 3 ms 4392 KiB
test_01.txt AC 1 ms 4400 KiB
test_02.txt AC 1 ms 4556 KiB
test_03.txt AC 1 ms 4484 KiB
test_04.txt AC 1 ms 4496 KiB
test_05.txt AC 2146 ms 5548 KiB
test_06.txt AC 2142 ms 5524 KiB
test_07.txt AC 2107 ms 5520 KiB
test_08.txt AC 2109 ms 5380 KiB
test_09.txt AC 2134 ms 5464 KiB
test_10.txt AC 2127 ms 5524 KiB
test_11.txt AC 2134 ms 5412 KiB
test_12.txt AC 2132 ms 5508 KiB
test_13.txt AC 2101 ms 5524 KiB
test_14.txt AC 2092 ms 5448 KiB
test_15.txt AC 2107 ms 5580 KiB
test_16.txt AC 2099 ms 5580 KiB
test_17.txt AC 2084 ms 5412 KiB
test_18.txt AC 2069 ms 5464 KiB
test_19.txt AC 2083 ms 5424 KiB
test_20.txt AC 2088 ms 5424 KiB
test_21.txt AC 2110 ms 5412 KiB
test_22.txt AC 2100 ms 5412 KiB
test_23.txt AC 2078 ms 5524 KiB
test_24.txt AC 2104 ms 5548 KiB
test_25.txt AC 2144 ms 5424 KiB
test_26.txt AC 2144 ms 5576 KiB
test_27.txt AC 2144 ms 5580 KiB
test_28.txt AC 2144 ms 5500 KiB