Create rectanglesGiven a rectangle with dimensions N'M and an integer
K. You divide this rectangle into smaller sub-rectanglessuch that the given conditions are satisfied:
●Sub-rectangles must be parallel to the axis of the
larger rectangle with dimensions N*M.Every sub-rectangle has at least one edge on the
larger rectangle edge. Informally, there is no sub-rectangle that is surrounded by other sub-
rectangles.For a sub-rectangle with area S, the cost of this sub-
rectangle is (S-K)2Calculate the minimum total cost to divide the larger
rectangle into smaller sub-rectangles.Note: All sub-rectangles must have an integral length of
dimensions.Function description
Complete the solve function. This function takes thefollowing 3 parameters and returns the required
answer:• N. Represents the value of N
• M. Represents the value of M• K: Represents the value of K
Input format for custom testingNote: Use this input format if you are testing against
custom input or writing code In a language where wedon't provide boilerplate code.
. The first line contains 7, which represents thenumber of test cases.
. For each test case:
o The first line contains an integer N.o The second line contains an integer M.
o The third line contains an integer K.Output format
For each test case in a new line, print the answerrepresenting the minimum cost.
Constraints1≤T≤5
1≤N, M≤ 3001≤K≤ 104
Sample input1
44
15Sample output
1
The first test caseExplanation
The first line contains the number of test cases, T = 1.Given
• N=4• M = 4
K = 15Approach
• You can create one sub-rectangle of dimension 4'4.Thus, the cost of the sub-rectangle is (16-15)^2.
. Thus, the minimum cost is 1.
The following test cases are the actual test casesof this question that may be used to evaluate your
submission.
Sample input 1 >1
23
3Sample output 1
0
Sample input 2 1
14
7
Sample output 29
Note:Your code must be able to print the sample output from the
provided sample input. However, your code is run against
multiple hidden test cases. Therefore, your code must passthese hidden test cases to solve the problem statement.
LimitsTime Limit: 3.0 sec(s) for each input file
Memory Limit: 256 MBSource Limit: 1024 KB
ScoringScore is assigned if any testcase passes
Allowed LanguagesGo, Java 8, Java 14, Help me to these code
==========================
Answer:-
def solve(N, M, K):
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, M + 1):
dp[i][j] = float('inf')
for k in range(1, i + 1):
for l in range(1, j + 1):
if k == i and l == j:
continue
dp[i][j] = min(dp[i][j], (i - k + 1) * (j - l + 1) + dp[k][l] + dp[i - k][j] + dp[k][j - l])
dp[i][j] = min(dp[i][j], K ** 2)
return dp[N][M]
# Example usage
N1, M1, K1 = 4, 4, 15
print(solve(N1, M1, K1)) # Output: 1
N2, M2, K2 = 23, 3, 3
print(solve(N2, M2, K2)) # Output: 0
N3, M3, K3 = 14, 7, 7
print(solve(N3, M3, K3)) # Output: 29