PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mexomerf
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given N, find the largest possible area of a rectangle with integer sides whose perimeter is \leq N.
EXPLANATION:
N is quite small, so the answer can be just brute-forced.
That is, fix the length L and the breadth B, both between 0 and N.
For a fixed L and B, the perimeter of the rectangle is 2\cdot (L+B).
If 2\cdot (L+B) \leq N, this is a valid rectangle, with area is L\times B - so do \text{ans} = \max(\text{ans}, L\times B).
The complexity of this is \mathcal{O}(N^2), which is fast enough for the given constraints.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
ans = 0
for L in range(n+1):
for B in range(n+1):
if 2*(L+B) > n: break
ans = max(ans, L*B)
print(ans)