Проблема с оптимизацией кода

@MaxGlock · Регистрация: 21.03.2020

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

Решаю олимпиадную задачу:
Клиппи и Мерлин решили грабить банк, который представляет собой N расположенных в ряд банковских ячеек, пронумерованных последовательно числами от 1 до N.
С помощью своего друга Ровера, который работал в банке сторожевым псом, они добыли ключи от всех ячеек, а так же узнали, как много ценностей хранится в каждой ячейке.
Чтобы не вызывать лишних подозрений, Клиппи и Мерлин решили ограбить всего две ячейки — по одной на каждого. Также, чтобы охрана банка не почуяла неладного, они решили работать далеко друг от друга — между ними должно быть не меньше K банковских ячеек.
Входные данные:
В первой строке вводятся два числа — N ( 2 ≤N≤ 105) и K (0 ≤K<N− 1) соответственно. В второй строке вводятся N чисел ai(0 ≤ai≤ 109) — стоимости хранимых ценностей в ячейках от 1 до N соответственно.
Выходные данные:
Выведите два числа в возрастающем порядке — номера ячеек, которые нужно ограбить, чтобы суммарно украсть как можно более дорогие ценности, не вызвав при этом лишних подозрений. Если вариантов несколько выберите тот, в котором меньший номер вскрываемой ячейки был как можно ближе к единице, чтобы в экстренном случае покинуть банк как можно скорее. Если и таких вариантов несколько, выберите тот, в котором и больший номер вскрываемой ячейки был как можно меньше.
Примеры:
Ввод:
6 2
2 4 3 1 4 4
Вывод:
2 5

Код я написал:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def qwer():
    Q=list(map(int, input().split()))
    A=list(map(int, input().split()))
    N=Q[0]
    K=Q[1]
    maxv=0
    for i in range(N):
        for j in range(N):
            if i+j>=K:
                if maxv<A[i]+A[j] and i>j:
                    maxv=A[i]+A[j]
                    q=i+1
                    w=j+1
    print(str(min(q,w))+' '+str(max(q,w)))
    
qwer()

Принимающий код ругается на время исполнения программы. Помогите оптимизировать и ускорить код, пожалуйста

@Garry Galler · 31.03.2020, 20:03

Сообщение от nns1

Во первых в чём смысл функции

А тебе зачем? Смысл в том как правильно ограбить банк.

@nns1 · 01.04.2020, 11:26

Сообщение от MaxGlock

нет, r это число

Да, но k-это строка.

@MaxGlock · 01.04.2020, 11:31 **[ТС]**

Сообщение от nns1

Да, но k-это строка

k - число, обозначающее минимальное число ячеек между ячейками, которые нужно ограбить

@Garry Galler · 01.04.2020, 13:07

Сообщение от nns1

но k-это строка.

Ты на питоне хотя бы две строчки писал?
В Python нельзя сложить строку и число.

@nns1 · 01.04.2020, 15:52

Сообщение от MaxGlock

нет, r это число

Да, но k -это строка.

@Garry Galler · 01.04.2020, 15:54

nns1,
Тебя глючит?

@MaxGlock · 01.04.2020, 15:54 **[ТС]**

nns1, эммммммммммммммм

Сообщение от MaxGlock

k - число, обозначающее минимальное число ячеек между ячейками, которые нужно ограбить

беды с башкой...

@nns1 · 01.04.2020, 16:04

В первой строке вводятся два числа — N ( 2 ≤N≤ 105) и K (0 ≤K<N− 1) соответственно. В второй строке вводятся N чисел ai(0 ≤ai≤ 109) — стоимости хранимых ценностей в ячейках от 1 до N соответственно.
N чисел питон воспринимает как строку, k - это N чисел, а не одно.

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
def rob_1(a, k):
    n = len(a)
    p = [0] * n
    s = [0] * n
 
    i, j = 0, 0
 
    for i in range(n):
        if (a[i] > a[j]):
            p[i] = i
            j = i
        else:
            p[i] = p[j]
 
    j = n - 1
    for i in range(n - 1, -1, -1):
        if (a[i] >= a[j]):
            s[i] = i
            j = i
        else:
            s[i] = s[j]
 
    m, l, r = 0, 0, k + 1
    i = l
 
    for j in range(r, n):
        t = a[p[i]] + a[s[j]]
        if t > m:
            l = p[i]
            r = s[j]
            m = t
        i += 1
 
    return l, r
 
a = input()

Добавлено через 1 минуту

Сообщение от nns1

Да, но k -это строка.

Случайно отправил

@MaxGlock · 01.04.2020, 16:08 **[ТС]**

nns1, читай всю задачу внимательно!

Сообщение от MaxGlock

Также, чтобы охрана банка не почуяла неладного, они решили работать далеко друг от друга — между ними должно быть не меньше K банковских ячеек.

N - количество ячеек в банке
K - сколько ячеек должно быть между ними
Оба числа вводятся в одной строке, то есть:

Python
1
N, K = map(int, input().split())

@nns1 · 01.04.2020, 19:37

ok/

Добавлено через 3 часа 29 минут
Можешь пж прислать фул код?

@Garry Galler · 01.04.2020, 19:46

Сообщение от nns1

Можешь пж прислать фул код?

Здесь полный код. Может попробуешь включить мозги?

@nns1 · 01.04.2020, 19:49

У меня при тесте из задачи выдаёт 2 и 8 вместо 2 и 5

Добавлено через 33 секунды

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
def rob_1(a, k):
    n = len(a)
    p = [0] * n
    s = [0] * n
 
    i, j = 0, 0
 
    for i in range(n):
        if (a[i] > a[j]):
            p[i] = i
            j = i
        else:
            p[i] = p[j]
 
    j = n - 1
    for i in range(n - 1, -1, -1):
        if (a[i] >= a[j]):
            s[i] = i
            j = i
        else:
            s[i] = s[j]
 
    m, l, r = 0, 0, k + 1
    i = l
 
    for j in range(r, n):
        t = a[p[i]] + a[s[j]]
        t = int(t)
        if t > m:
            l = p[i]
            r = s[j]
            m = t
        i += 1
 
    return l, r
n, k = map(int, input().split())
a = input()
print(rob_1(a,k))

@Garry Galler · 01.04.2020, 20:36

Не по теме:

Mih1nya, nns1,
Свалите уже с форума- недоучки.

@Mih1nya · 01.04.2020, 20:41

Garry Galler, мне не понятно. Я буквально недавно начал изучать питон. Скинь полный код, пожалуйста.
Заранее огромное спасибо!

@nns1 · 01.04.2020, 20:47

Code
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
N, k = map(int, input().split())
a = input()
n = len(a)
p = [0] * n
s = [0] * n
i, j = 0, 0
for i in range(n):
        if (a[i] > a[j]):
            p[i] = i
            j = i
        else:
            p[i] = p[j]
j = n - 1
for i in range(n - 1, -1, -1):
        if (a[i] >= a[j]):
            s[i] = i
            j = i
        else:
            s[i] = s[j]
m, l, r = 0, 0, k + 1
i = l
for j in range(r, n):
        t = a[p[i]] + a[s[j]]
        if int(t) > int(m):
            l = p[i]
            r = s[j]
            m = t
        i += 1
print(l, r)

Что не так в этом коде?

Добавлено через 55 секунд
При тесте из задачи ответ 2 и 8.

Добавлено через 17 секунд
Это же твой код

Добавлено через 3 минуты
Игноришь?

@Garry Galler · 01.04.2020, 21:25

Сообщение от nns1

При тесте из задачи ответ 2 и 8.

Нет.

Python
1
2
3
arr = list(map(int,'2 4 3 1 4 4'.split()))
k = 2
rob_1(arr,k)

Code
1
(1, 4)

1 и 4 это правильный ответ. А для особо не одаренных там есть коммент: +1 добавьте сами, так как код выдает реальные индексы, а не нумерацию с единицы.

@nns1 · 01.04.2020, 21:40

1 и 4 - правильный ответ?

@Garry Galler · 01.04.2020, 21:47

Сообщение от nns1

1 и 4 - правильный ответ?

Тебя заклинило?
Да, это правильный ответ. 1 и 4 индекс списка.

@nns1 · 01.04.2020, 21:51

Сообщение от Garry Galler

Тебя заклинило?
Да, это правильный ответ. 1 и 4 индекс списка.

Какого списка? И к каким индексам приписывать +1?

@Garry Galler · 01.04.2020, 21:53

Тема закрыта.

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@Garry Galler 5439 / 3860 / 1215 Регистрация: 28.10.2013 Сообщений: 9,552 Записей в блоге: 1
	01.04.2020, 15:54
	nns1, Тебя глючит? 0

@nns1 2 / 1 / 1 Регистрация: 09.03.2020 Сообщений: 16
	01.04.2020, 19:37
	ok/ Добавлено через 3 часа 29 минут Можешь пж прислать фул код? 0

@Garry Galler
	01.04.2020, 20:36
	Не по теме: Mih1nya, nns1, Свалите уже с форума- недоучки. 0

@Mih1nya Заблокирован
	01.04.2020, 20:41
	Garry Galler, мне не понятно. Я буквально недавно начал изучать питон. Скинь полный код, пожалуйста. Заранее огромное спасибо! 1

@nns1 2 / 1 / 1 Регистрация: 09.03.2020 Сообщений: 16
	01.04.2020, 21:40
	1 и 4 - правильный ответ? 0

@Garry Galler 5439 / 3860 / 1215 Регистрация: 28.10.2013 Сообщений: 9,552 Записей в блоге: 1
	01.04.2020, 21:53
	Тема закрыта. 0