Имеется решение на языке Python, но оно использует слишком много памяти.
Наследники
Король Т-Царства Олег в 2024 году празднует свое шестидесятилетие. В связи с этим его заинтересовал вопрос наследства. На данный момент Т-Царство представляет из себя прямоугольник w*h, разделенный на графства параллельно своим сторонам. По вертикали разрезы проходят в координатах x1,x2,x3, по горизонтали в y1, y2, y3....
В первой строке вводятся два числа размеры Т-Царства.
Во второй строке вводятся два числа количество вертикальных и горизонтальных делений на графства.
В третьей строке вводится одно число количество сыновей.
В четвертой строке вводятся чисел координаты делений на графства по вертикали.
В пятой строке вводятся чисел координаты делений на графства по горизонтали.
Вот пример решения
import heapq
import gc
def f(x):
return (x[i + 1] - x for i in range(len(x) - 1))
def Solution(w, h, n, m, k, x, y):
# Освобождаем память от ненужных переменных
del w, h, n, m
gc.collect()
widths = f(x)
heights = f
# Очистка памяти от ненужных переменных
del x, y
gc.collect()
# Поддерживаем кучу размера k
heap = []
for width in widths:
for height in heights:
area = width * height
if len(heap) < k:
heapq.heappush(heap, area)
else:
break
mi = min(heap)
# Освобождаем память от ненужных переменных
del widths, heights
gc.collect()
return heap, mi
if __name__ == "__main__":
w, h = map(int, input().split())
n, m = map(int, input().split())
k = int(input())
if n > 0:
x = list(map(int, input().split()))
else:
x = []
if m > 0:
y = list(map(int, input().split()))
else:
y = []
x = [0] + x + [w]
y = [0] + y + [h]
mi, ma = Solution(w, h, n, m, k, x, y)
print(mi, ma)
Можете переписать его на C++
Наследники
Король Т-Царства Олег в 2024 году празднует свое шестидесятилетие. В связи с этим его заинтересовал вопрос наследства. На данный момент Т-Царство представляет из себя прямоугольник w*h, разделенный на графства параллельно своим сторонам. По вертикали разрезы проходят в координатах x1,x2,x3, по горизонтали в y1, y2, y3....
В первой строке вводятся два числа размеры Т-Царства.
Во второй строке вводятся два числа количество вертикальных и горизонтальных делений на графства.
В третьей строке вводится одно число количество сыновей.
В четвертой строке вводятся чисел координаты делений на графства по вертикали.
В пятой строке вводятся чисел координаты делений на графства по горизонтали.
Вот пример решения
import heapq
import gc
def f(x):
return (x[i + 1] - x for i in range(len(x) - 1))
def Solution(w, h, n, m, k, x, y):
# Освобождаем память от ненужных переменных
del w, h, n, m
gc.collect()
widths = f(x)
heights = f
# Очистка памяти от ненужных переменных
del x, y
gc.collect()
# Поддерживаем кучу размера k
heap = []
for width in widths:
for height in heights:
area = width * height
if len(heap) < k:
heapq.heappush(heap, area)
else:
break
mi = min(heap)
# Освобождаем память от ненужных переменных
del widths, heights
gc.collect()
return heap, mi
if __name__ == "__main__":
w, h = map(int, input().split())
n, m = map(int, input().split())
k = int(input())
if n > 0:
x = list(map(int, input().split()))
else:
x = []
if m > 0:
y = list(map(int, input().split()))
else:
y = []
x = [0] + x + [w]
y = [0] + y + [h]
mi, ma = Solution(w, h, n, m, k, x, y)
print(mi, ma)
Можете переписать его на C++