Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package org.example;
- import java.util.Map;
- import java.util.Scanner;
- import java.util.TreeMap;
- public class Main {
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int M = scanner.nextInt();
- int N = scanner.nextInt();
- int A = scanner.nextInt();
- int B = scanner.nextInt();
- int[][] matrix = new int[M][N];
- for (int i = 0; i < M; i++) {
- for (int j = 0; j < N; j++) {
- matrix[i][j] = scanner.nextInt();
- }
- }
- int[][] prefixSum = new int[M + 1][N + 1];
- for (int i = 1; i <= M; i++) {
- for (int j = 1; j <= N; j++) {
- prefixSum[i][j] = matrix[i - 1][j - 1]
- + prefixSum[i - 1][j]
- + prefixSum[i][j - 1]
- - prefixSum[i - 1][j - 1];
- }
- }
- System.out.println(getSum(prefixSum, 1, 1, 2, 3));
- TreeMap<Integer, Integer> rectangleSums= new TreeMap<>();
- for (int x1 = 0; x1 < M - 1; x1++) {
- for (int y1 = 0; y1 < N; y1++) {
- for (int x2 = x1; x2 < M; x2++) {
- for (int y2 = 0; y2 < N; y2++) {
- int sum = getSum(prefixSum, x1, y1, x2, y2);
- if ((x2 <= x1 && y2 < y1) || sum > B) {
- continue;
- }
- rectangleSums.put(sum, rectangleSums.getOrDefault(sum, 0) + 1);
- }
- }
- }
- }
- TreeMap<Integer, Integer> prefixMap = new TreeMap<>(rectangleSums);
- prefixMap.put(0, 0);
- for (Map.Entry<Integer, Integer> entry : rectangleSums.entrySet()) {
- prefixMap.put(prefixMap.lastKey() + entry.getKey(), prefixMap.get(prefixMap.lastKey()) + entry.getValue());
- }
- }
- private static int getSum(int[][] prefixSum, int x1, int y1, int x2, int y2) {
- return prefixSum[x2][y2]
- - prefixSum[x1 - 1][y2]
- - prefixSum[x2][y1 - 1]
- + prefixSum[x1 - 1][y1 - 1];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement