Небоскрёбы

@Retry32 · Регистрация: 05.05.2021

Студворк — интернет-сервис помощи студентам

В Берляндии активно застраивается окраина столицы. Компания "Kernel Panic" руководит постройкой жилого комплекса из небоскрёбов в Новой Берлскве. Все небоскрёбы строятся вдоль шоссе. Известно, что компания уже купила n участков возле шоссе и готовится возводить небоскрёбы, по одному зданию на один участок.

Архитекторы при планировании зданий должны учитывать несколько требований. Во-первых, поскольку земля на каждом участке имеет разные свойства, для каждого небоскрёба есть своё ограничение по количеству этажей, которое он может иметь. Во-вторых, согласно дизайн-коду города, недопустима ситуация, когда для какого-то небоскрёба сразу по обе стороны от него есть небоскрёбы выше него.

Более формально, пронумеруем участки целыми числами от 1 до n. Тогда у небоскрёба на участке с номером i количество этажей ai не может быть запланировано больше mi, и также не может быть, что на плане существуют два участка с номерами j и k таких, что j<i<k и aj>ai<ak.

Компания хочет, чтобы суммарное количество этажей в построенных небоскрёбах было как можно больше. Помогите ей спланировать количество этажей для каждого небоскрёба оптимальным образом, то есть так, чтобы выполнялись все ограничения, и при этом суммарное количество этажей было максимально возможным среди всех возможных вариантов, удовлетворяющих данным ограничениям.

Входные данные

В первой строке задано одно целое число n (1≤n≤500 000) — количество участков.

Вторая строка содержит n целых чисел. i-е число задает значение mi (1≤mi≤109) — максимально возможное количество этажей для небоскрёба на участке i.

Выходные данные

Выведите n чисел ai — количества этажей в плане для каждого небоскрёба такие, что выполняются все ограничения, а суммарное количество этажей во всех небоскрёбах максимально возможное. Если возможных ответов несколько, выведите любой.

Ограничения
Время выполнения: 3 секунды

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def rmin(a,n) :
    ans = [-1] * (n + 2)
    st = [0]
    res = []
    for i in range(1, n + 1):
        while a[st[-1]] > a[i]:
            ans[st.pop()] = n + 1 - i
        st.append(i)
    for i in range(1, n + 1):
         res.append(ans[i])
    return res
 
 
n = int(input())
inf = int(2e9) + 1
m = [int(x) for x in input().split()]
m = [-inf] + m + [-inf]
ar = rmin(m,n)
al = rmin(m[::-1],n)[::-1]
lm = [0 for i in range(n)]
rm = lm.copy()
###################################
#.  Вот этот цикл можно было завернуть в 'def rmin'
###################################
for i in range(n) :
    j = n - 1 - i
    lm[i] = m[i+1] * (i + 1)
    rm[j] = (i + 1) * m[j+1]
    if al[i] != -1 :
        lm[i] += lm[al[i]-1] - m[i+1] * al[i]
    if ar[j] != -1 :
        rm[j] += rm[n-ar[j]] - m[j+1] * ar[j]
###############################
th = 0
for i in range(n) :
    tmp = lm[i] + rm[i] - m[i+1]
    #print(tmp,th)
    if tmp > th :
        th = tmp
        tind = i + 1
i = tind + 1
#print(i,m)
while i < n :
    if m[i+1] > m[i] :
        m[i+1] = m[i]
    i += 1
i = tind
while i > 0 :
    if m[i-1] > m[i] :
        m[i - 1] = m[i]
    i -= 1
print(*m[1:n+1])

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

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем