Advertisement
7DemOn7

Untitled

Nov 19th, 2024 (edited)
38
0
6 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.15 KB | None | 0 0
  1. package org.example;
  2.  
  3. import java.util.Map;
  4. import java.util.Scanner;
  5. import java.util.TreeMap;
  6.  
  7. public class Main {
  8.     public static void main(String[] args) {
  9.         Scanner scanner = new Scanner(System.in);
  10.  
  11.         int M = scanner.nextInt();
  12.         int N = scanner.nextInt();
  13.         int A = scanner.nextInt();
  14.         int B = scanner.nextInt();
  15.         int[][] matrix = new int[M][N];
  16.         for (int i = 0; i < M; i++) {
  17.             for (int j = 0; j < N; j++) {
  18.                 matrix[i][j] = scanner.nextInt();
  19.             }
  20.         }
  21.  
  22.         int[][] prefixSum = new int[M + 1][N + 1];
  23.         for (int i = 1; i <= M; i++) {
  24.             for (int j = 1; j <= N; j++) {
  25.                 prefixSum[i][j] = matrix[i - 1][j - 1]
  26.                         + prefixSum[i - 1][j]
  27.                         + prefixSum[i][j - 1]
  28.                         - prefixSum[i - 1][j - 1];
  29.             }
  30.         }
  31.         System.out.println(getSum(prefixSum, 1, 1, 2, 3));
  32.         TreeMap<Integer, Integer> rectangleSums= new TreeMap<>();
  33.         for (int x1 = 0; x1 < M - 1; x1++) {
  34.             for (int y1 = 0; y1 < N; y1++) {
  35.                 for (int x2 = x1; x2 < M; x2++) {
  36.                     for (int y2 = 0; y2 < N; y2++) {
  37.                         int sum = getSum(prefixSum, x1, y1, x2, y2);
  38.                         if ((x2 <= x1 && y2 < y1) || sum > B) {
  39.                             continue;
  40.                         }
  41.                         rectangleSums.put(sum, rectangleSums.getOrDefault(sum, 0) + 1);
  42.                     }
  43.                 }
  44.             }
  45.         }
  46.  
  47.         TreeMap<Integer, Integer> prefixMap = new TreeMap<>(rectangleSums);
  48.         prefixMap.put(0, 0);
  49.         for (Map.Entry<Integer, Integer> entry : rectangleSums.entrySet()) {
  50.             prefixMap.put(prefixMap.lastKey() + entry.getKey(), prefixMap.get(prefixMap.lastKey()) + entry.getValue());
  51.         }
  52.  
  53.     }
  54.  
  55.     private static int getSum(int[][] prefixSum, int x1, int y1, int x2, int y2) {
  56.         return prefixSum[x2][y2]
  57.                 - prefixSum[x1 - 1][y2]
  58.                 - prefixSum[x2][y1 - 1]
  59.                 + prefixSum[x1 - 1][y1 - 1];
  60.     }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement