# 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++) {