Пожалуйста помогите улучшить решение задачи

Question

Я уже написал код на phyton, но он не до конца работает. Помогите пожалуйста

Задача:

Условие n строителей несут одну балку. И вдруг перед ними оказываются k ям. Строители, не долго думая, двинулись прямиком через эти ямы. Если вдруг один человек оказался над ямой, то он немедленно вцепляется в балку, а остальные продолжают идти, и таким образом строители пытаются преодолеть ямы.Но строители не всемогущи, поэтому если в какой-то момент суммарный вес строителей, находящихся над пропастью, превышает суммарный вес строителей, стоящих на земле, то у остальных не хватает сил выдержать висящих на балке, и те падают в яму. Благо яма не глубокая, поэтому все отделаются легким испугом. Когда хотя бы один человек падает, все остальные прекращают движение, и ваше наблюдение заканчивается.

Формат входных данных Первая строка входного файла содержит два числа: n количество строителей, k количество ям. Вторая строка список координат относительно начала балки строителей и их веса: p1, w1, ..., pn, wn. Координаты рабочих считаются от левого конца балка Третья строка координаты краёв ям: l1, r1, ..., lk, rk.

Формат выходных данных Выходной файл должен содержать одно число - количество упавших строителей

Стандартный вход:

3 1
0 1 1 1 2 1
1 1

Стандартный выход:

Я уже написал код, который проходит по нескольким тестам, но возникают ошибки в других тестах

вот код на python:

n, k = map(int, input().split())
builders = list(map(int, input().split()))
holes = list(map(int, input().split()))

fallen_count = 0
total_weight = 0
max_weight = 0
i = 0
p=0
sch = 1
all_w = 0

for j in range(n):
    all_w = all_w + builders[sch]
    sch += 2
count = 0
for j in range(n):
    if holes[i] <= builders[p] <= holes[i+1] and builders[p+1]>(all_w-builders[p+1]):
        count += 1
    p += 2

print(count)

Очень надеюсь на помощь Заранее спасибо

PS Ограничения

0<N∗K≤10**6
0<li,ri≤10**9
0<pi,<pi+1≤10**9
1<∑wi≤10**9

Answer 1

Ограничение 0<N∗K≤10**6 облегчает задачу. Пусть условная скорость движения 1 метр в секунду. Сгенерируем все события для каждого строителя

for i in range(n):
    delta = builder[-1].pos-builder[i].pos
    for j in range(k):
        events.append((delta + hole[j].start, -1, builder[i].weight))
        events.append((delta + hole[j].end, 1, builder[i].weight))

Отсортируем события по времени - первому элементу кортежа, а при равенстве учтём второй элемент (это будет применено автоматически).

Пройдём по списку событий. На каждом шаге отнимаем от количества висящих значение tuple[1], а от веса висящих значение tuple[1]*tuple[2]. Если оно превысило половину общего веса - упали. Количество в это момент известно.

Как это работает:

При движении i-й строитель встречает начало или конец ямы с позицией pos в момент времени delta+pos (delta - сколько он сначала прошёл до старта)

Вот все эти события для всех людей и краёв ям заранее генерируем и записываем в events в виде кортежа - время, +/-1 - признак начала или конца ямы, вес строителя.

После сортировки мы имеем правильную последовательность событий во времени.

Когда мы встречаем событие с признаком -1, то человек повисает, его вес добавляется к висячим. Когда мы встречаем событие с признаком +1, то человек выходит из ямы, его вес убирается из общего веса висящих.

Вот пара подобных задач:

Как можно оптимизировать задачу?
Python, задание найти пересечения времени

БЛОГ НА HUSL

Пожалуйста помогите улучшить решение задачи

Ответы (1 шт):