Submission #76475334

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
using pii = pair<ll, ll>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using mint = modint998244353;
// using mint = modint1000000007;
#define endl '\n'
#define OVERLOAD_REP(a, b, c, d, name, ...) name
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define REP0(x) for (ll _rep_counter = 0; _rep_counter < (x); ++_rep_counter)
#define REP1(i, x) for (ll i = 0; (i) < (x); ++(i))
#define REP2(i, l, r) for (ll i = (l); (i) < (r); ++(i))
#define REP3(i, l, r, c) for (ll i = (l); ((c) > 0 ? (i) < (r) : (i) > (r)); i += (c))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const ll INF = LLONG_MAX / 4;
vi dx = {1, 0, -1, 0, 1, 1, -1, -1};
vi dy = {0, 1, 0, -1, 1, -1, 1, -1};
vc alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vc ALPHABET = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

void io_setup()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(16);
}

int main(void)
{
    io_setup();
    int h, w, k;
    cin >> h >> w >> k;
    vvi g(h, vi(w));
    ll ans = 0;
    rep(i, h){
      string s;
      cin >> s;
      rep(j, w){
        g[i][j] = s[j]-'0';
      }
    }
    
    vvi sum(h+1, vi(w));
    rep(i, h) {
        rep(j, w) {
            sum[i + 1][j] = sum[i][j] + g[i][j];
        }
    }
    rep(i, h+1){
      rep(j, w){
        cerr << sum[i][j];
      }
      cerr << endl;
    }
    
    rep(r1, h){
      rep(r2, r1, h){
        vi col(w);
        rep(j, w) {
          col[j] = sum[r2 + 1][j] - sum[r1][j];
        }
        unordered_map<ll, ll> mp;
        mp.reserve(w * 2);
        ll pref = 0;
        mp[0] = 1;
        rep(j, w) {
          pref += col[j];
          auto it = mp.find(pref - k);
          if (it != mp.end()) {
            ans += it->second;
          }
          mp[pref]++;
        }
      }
    }
    cout << ans << endl;

}

Submission Info

Judge Result