Untitled
unknown
plain_text
a month ago
3.2 kB
3
Indexable
Never
import java.io.*; import java.util.*; import java.lang.Math; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; public class Solution { // Function to get maximum sum of beauties of two non-intersecting sub-grids public static int get_ans(int N, List<List<Integer>> A) { int[][] grid = new int[N][N]; // Convert the List to a 2D Array for easier manipulation for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { grid[i][j] = A.get(i).get(j); } } // Precompute the prefix sums of the grid int[][] prefixSum = new int[N + 1][N + 1]; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { prefixSum[i][j] = grid[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]; } } int K = Math.min(N, N); // Assuming the maximum number of non-overlapping sub-grids is the minimum of N as size of S is K or N // Initialize the DP array where dp[k][j] is the maximum beauty using exactly k sub-grids till column j int[][] dp = new int[K + 1][N + 1]; for (int[] row : dp) { Arrays.fill(row, Integer.MIN_VALUE/2); } dp[0][0] = 0; // Calculate the DP array for (int col = 1; col <= N; col++) { for (int k = 1; k <= K; k++) { for (int size = 1; size <= N; size++) { for (int si = 0; si + size <= N; si++) { for (int sj = 0; sj + size <= col; sj++) { int ei = si + size - 1; int ej = sj + size - 1; int subGridSum = getSum(prefixSum, si, sj, ei, ej); dp[k][col] = Math.max(dp[k][col], dp[k - 1][sj] + subGridSum); } } } } } int maxBeauty = Integer.MIN_VALUE; for (int j = 0; j <= N; j++) { maxBeauty = Math.max(maxBeauty, dp[K][j]); } if (maxBeauty < 0) { maxBeauty += 1000000; } return maxBeauty; } // Compute the sum of sub-grid using precomputed prefix sums private static int getSum(int[][] prefixSum, int si, int sj, int ei, int ej) { return prefixSum[ei + 1][ej + 1] - prefixSum[ei + 1][sj] - prefixSum[si][ej + 1] + prefixSum[si][sj]; } public static void main(String[] args) { Scanner scan = new Scanner (System.in); int N = Integer.parseInt(scan.nextLine().trim()); int K = Integer.parseInt(scan.nextLine().trim()); List<List<Integer>> A = new ArrayList<>(N); for (int i = 0; i < N; i++) { A.add( Arrays.asList(scan.nextLine().trim().split(" ")) .stream().map(s -> Integer.parseInt(s)).collect(toList()) ); } int result = get_ans(N, A); System.out.println(result); } }
Leave a Comment