Submission #76475752

---

Source Code Expand

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        int[][] grid = new int[H][W];
        for (int i = 0; i < H; i++) {
            String line = br.readLine();
            for (int j = 0; j < W; j++) {
                grid[i][j] = line.charAt(j) - '0';
            }
        }
        
        int[][] vsum = new int[H][W];
        for (int j = 0; j < W; j++) {
            vsum[0][j] = grid[0][j];
            for (int i = 1; i < H; i++) {
                vsum[i][j] = vsum[i-1][j] + grid[i][j];
            }
        }
        
        long count = 0;
        
        
        for (int r1 = 0; r1 < H; r1++) {
            for (int r2 = r1; r2 < H; r2++) {
        
                HashMap<Integer, Integer> freq = new HashMap<>();
                freq.put(0, 1);
                int prefSum = 0;
                
                for (int j = 0; j < W; j++) {
                    int colVal = vsum[r2][j] - (r1 > 0 ? vsum[r1-1][j] : 0);
                    prefSum += colVal;
                    
                    count += freq.getOrDefault(prefSum - K, 0);
                    
                    freq.put(prefSum, freq.getOrDefault(prefSum, 0) + 1);
                }
            }
        }
        
        System.out.println(count);
    }
}

Submission Info

Judge Result