Дописать ф-ю, у которой параметры - это 4 списка.
p - количество людей в каждом городе (int >0)
x - расположение каждого города (int>0)
y - расположение каждого облака (int>0)
r - радиус каждого облака (int), соответственно начало и конец облака c индексом i (Yi-Ri, Yi+Ri).
Необходимо удалить одно облако так, чтобы общее количество людей в городах вне облаков стало максимально возможным.
В списке участников, прошедших все тесты, решения в основном на с++ и java (на каждые 20 участников c максимум баллов - 1 питонист).
Первый же питонист в топе списка, как оказалось, переписал полностью вот этот код ниже, который трогать не предполагается и соответственно его ф-я принимает другие параметры, переделанные списки и прочее.
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
p = list(map(int, input().rstrip().split()))
x = list(map(int, input().rstrip().split()))
m = int(input())
y = list(map(int, input().rstrip().split()))
r = list(map(int, input().rstrip().split()))
result = maximumPeople(p, x, y, r)
fptr.write(str(result) + '\n')
fptr.close()
Мое решение ниже проходит всего 11 тестов из 28, когда начинаются списки из 200 000 элементов то Terminated due to timeout error.
В связи с чем у меня вопрос, эту задачу в принципе возможно решить на Python? И если да, то какой подход использовать?
def maxSun(p, x, y, r):
# Return the maximum number of people that will be in sunny towns after removing exactly one cloud.
from collections import defaultdict
from itertools import chain
lY,lX=range(len(y)),range(len(x))
by_length=sorted(((y[i] - r[i], y[i] + r[i]) if (y[i] - r[i]) >= 0
else (0, y[i] + r[i])
for i in lY), key=lambda x: x[1]- x[0], reverse=True)
if not by_length[1:]: # remove first largest range
return sum(p)
d=defaultdict(list)
for tupl in by_length[1:]:
if not d:
for i in lX:
if x[i]<tupl[0] or x[i]>tupl[1]:
d[x[i]].append(p[i]) #X beyond second largest range; form a dict
if not d: #no X-elements beyond second largest range
return 0
else:
for X in d.copy(): #exclude X within other ranges from a dict
if X >=tupl[0] and X<=tupl[1]:
del d[X]
if not d:
return 0
return sum(chain(*d.values()))
