提出 #76469151

---

ソースコード 拡げる

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

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int h, w, k;
    cin>>h>>w>>k;
    vector<string> s(h);
    for(int i=0; i<h; i++){
        cin>>s[i];
    }
    vector<vector<int>> pre2D(h+1, vector<int>(w+1, 0));
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            int x = s[i-1][j-1]-'0';
            pre2D[i][j] = x + pre2D[i-1][j] + pre2D[i][j-1] - pre2D[i-1][j-1];
        }
    }
    int ans = 0;
    vector<int> count(h*w+1, 0);

    for(int i=1; i<=h; i++){
        for(int j=i; j<=h; j++){
            count[0]=1;
            for(int c=1; c<=w; c++){
                int sum = pre2D[j][c] - pre2D[i-1][c];
                if(sum>=k){
                    ans += count[sum-k];
                }
                count[sum]++;
            }

            count[0]=0;
            for(int c=1; c<=w; c++){
                int sum = pre2D[j][c]-pre2D[i-1][c];
                count[sum]=0;
            }

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

提出情報

ジャッジ結果