ENG
RUS
Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум
Обсуждение задачи
1005
. Куча камней
Python3 На третьем тесте превышаю лимит времени
Послано
Desserg
31 окт 2019 14:22
Как можно оптимизировать или перебором в лоб будет быстрее?
__________________________________________________________
# Считываем данные
N = int(input())
weight = list(map(int, input().split(' ')))
'''
Задача разбиения множества чисел
Псевдополиномиальный алгоритм
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D1%80%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
'''
# Создаем массив P
S = [0] + weight
K = sum(S)
X = K//2+1
Y = len(S)+1
P = []
for i in range(X):
P.append([])
for j in range(Y):
if i == 0:
P[i].append(1)
else:
P[i].append(0)
for i in range(1, X):
for j in range(1, Y):
if (i - S[j-1]) >= 0:
P[i][j] = (P[i][j-1] or P[i - S[j-1]][j-1])
else:
P[i][j] = (P[i][j-1])
for i in range(X-1, -1, -1):
if 1 in P[i]:
print(K - 2*i)
break
Re: Python3 На третьем тесте превышаю лимит времени
Послано
Desserg
13 ноя 2019 11:22
Понял в чем состоит третий тест. Теперь уперся в предел времени TLE на четвертом...
© 2000–2024
Timus Online Judge Team
. Все права защищены.