# Untitled

unknown
plain_text
2 months ago
3.6 kB
2
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 List to a 2D Array
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] = A.get(i).get(j);
}
}

// Precompute the beauty for all possible sub-grids
int[][][][] beauty = new int[N][N][N][N];
for (int si = 0; si < N; si++) {
for (int sj = 0; sj < N; sj++) {
for (int ei = si; ei < N; ei++) {
for (int ej = sj; ej < N; ej++) {
for (int i = si; i <= ei; i++) {
for (int j = sj; j <= ej; j++) {
beauty[si][sj][ei][ej] += grid[i][j];
}
}
}
}
}
}

int[][] dp = new int[1 << N][N];
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = Integer.MIN_VALUE / 2;
}
}

for (int j = 0; j < N; j++) {
for (int si = 0; si < N; si++) {
for (int sj = 0; sj <= j; sj++) {
for (int ei = si; ei < N; ei++) {
for (int ej = sj; ej <= j; ej++) {
int newState = subgridMask | (1 << j);
dp[newState][ej] = Math.max(dp[newState][ej], beauty[si][sj][ei][ej]);
}
}
}
}
}

for (int state = 0; state < (1 << N); state++) {
for (int last = 0; last < N; last++) {
for (int j = last + 1; j < N; j++) {
if ((state & (1 << j)) != 0) continue;
int newState = state | (1 << j);
dp[newState][j] = Math.max(dp[newState][j], dp[state][last]);
}
}
}

int maxBeauty = Integer.MIN_VALUE / 2;
int K = N;  // Assuming K is equal to N as per problem assumption

for (int state = 0; state < (1 << N); state++) {
if (Integer.bitCount(state) == K) {
for (int last = 0; last < N; last++) {
maxBeauty = Math.max(maxBeauty, dp[state][last]);
}
}
}

if (maxBeauty < 0) {
maxBeauty += 1000000;
}

return maxBeauty;
}

private static int mask(int si, int ei) {
int result = 0;
for (int i = si; i <= ei; i++) {
result |= (1 << i);
}
return result;
}

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