Вопрос Как решить задачу на олимпиаде по программированию?

[shpipon]

Имеется решение на языке 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++

 

[ChevVv]

Количество &#34;графств&#34; не должно быть меньше количества сыновей. С оставшимися-то что делать? Надо упорядочить &#34;графства&#34; по убыванию значения площади и отобрать по количеству сыновей. То есть ответом будет разница нулевого и последнего. До этого вычислить эти площади по координатам и составить список (как-нибудь &#34;графства&#34; идентифицировав, например, перенумеровав). Для сокращения занятой памяти надо упорядочить список длин (отрезков) на каждой стороне по убыванию и, составляя список площадей, сразу создавать его убывающим и равным по длине количеству сыновей.

 

[Роман1999]

Ты условие не до конца скинул - в чём задача то?

 

[Merujan99]

А задача-то где? Ты дал только описание исходных данных. Без описания того, что с этими данными нужно делать и что должно получиться в результате.

N.B. Спасибо, добавил, что должно получиться. Но где описание правил, по которым графства распределяются между сыновьями? Может быть, старший сын получит вообще всё и младшему ничего не достанется?

В заведомо не укладывающемся в лимиты Python-коде бессмысленно разбираться: раз &#34;слишком много памяти&#34;, значит надо не &#34;переписать на C++&#34; (опять будет &#34;слишком много памяти&#34, а найти другой способ решения.

 

[zaver]

Да поможет вам Бог??????????