Submission #76506670

---

Source Code Expand

// #define ATCODER
// #define BOOST

// #define MOD1000000007

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#ifdef MOD1000000007
#define MOD 1000000007
#else
#define MOD 998244353
#endif

#ifdef ATCODER
#include <atcoder/all>
using namespace atcoder;
#ifdef MOD1000000007
using mint = modint1000000007;
#else
using mint = modint998244353;
#endif
#endif

#ifdef BOOST
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
using Bint = cpp_int;
using Real32 = number<cpp_dec_float<32>>;
#define repb(i, r) for(Bint i = 0; (Bint)(i) < (Bint)(r); i++)
#define perb(i, r) for(Bint i = (Bint)(r); (Bint)(i) > 0; i++)
#endif

// c++テンプレ
// https://hackmd.io/J0ohc60AQaKfZJMJdT6sUg
// https://dekavit.net
// https://atcoder.github.io/ac-library/document_ja/index.html

#include <bits/stdc++.h>
#define repp(i, l, r) for(long long i = (long long)(l); i < (long long)(r); i++)
#define perp(i, r, l) for(long long i = (long long)(r); i > (long long)(l); i--)
#define rep(i, r) for(long long i = 0; (long long)(i) < (long long)(r); i++)
#define per(i, r) for(long long i = (long long)(r); (long long)(i) > 0; i--)
#define INF (1LL<<62)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;


// 2次元累積和
// [r1,r2)x[c1,c2)の範囲の総和をO(1)で求められる
// 前計算O(HW),クエリの処理O(1)
template<typename T>
class cumulative_sum_2d {
  private:
    vector<vector<T>> v;
    int H,W;
    T e = 0;

  public:
    cumulative_sum_2d(int h, int w) {
      v.resize(h+1);
      for(auto &x : v) x.assign(w+1,e);
      H = h, W = w;
    }
    cumulative_sum_2d(vector<vector<T>> &A) {
      H = A.size(), W = A[0].size();
      v.resize(H+1);
      for(auto &x : v) x.assign(W+1,e);
      for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
          v[i+1][j+1] = A[i][j];
        }
      }
    }
    // v[r][c]にxを代入
    // O(1)
    void set(int r, int c, T x) {
      if(0<=r&&r<H&&0<=x&&c<W) v[r+1][c+1] = x;
    }
    // 累積和を構築
    // O(HW)
    void build() {
      for(int i = 1; i <= H; i++) {
        for(int j = 1; j <= W; j++) {
          v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
        }
      }
    }
    // [r1,r2)x[c1,c2)の総和を返す
    // O(1)
    T prod(int r1, int c1, int r2, int c2) {
      if(0<=r1&&r1<r2&&r2<=H&&0<=c1&&c1<c2&&c2<=W){
        return v[r2][c2] - v[r2][c1] - v[r1][c2] + v[r1][c1];
      }else{
        cerr<<"Out of range."<<endl;
        return e;
      }
    }

    vector<T> &operator[](int i) { return this->v[i]; }
};

int solver(){
  ll H,W,K;
  cin>>H>>W>>K;
  vector<string> S(H);
  vector<vector<ll>> A(H,vector<ll>(W));
  rep(i,H){
    cin>>S[i];
    rep(j,W){
      A[i][j] = S[i][j]-'0';
    }
  }
  cumulative_sum_2d<ll> C(A);
  C.build();
  unordered_map<ll,ll> cnt;
  ll ans = 0;
  repp(h2,1,H+1){
    repp(h1,1,h2+1){
      rep(w,W+1){
        cnt[C[h2][w]-C[h1-1][w]]++;
      }
      repp(w1,1,W+1){
        auto temp = C[h2][w1-1]-C[h1-1][w1-1];
        cnt[temp]--;
        temp = K + C[h2][w1-1] - C[h1-1][w1-1];
        ans += cnt[temp];
      }
      cnt[C[h2][W]-C[h1-1][W]] = 0;
    }
  }
  cout<<ans<<endl;
  return 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(10);
  solver();
  return 0;
}

Submission Info

Judge Result