Submission #385789

#	Time	Username	Problem	Language	Result	Execution time	Memory
385789		SansPapyrus683	Global Warming (CEOI18_glo)	Cpython 3	100 / 100	849 ms	25340 KiB

glo

from bisect import bisect_left

temp_num, max_cheating = [int(i) for i in input().split()]
temps = [int(i) for i in input().split()]
assert temp_num == len(temps)

pref_longest = []
min_endings = []
for i, t in enumerate(temps):
    pos = bisect_left(min_endings, t)
    pref_longest.append(pos + 1)
    if pos == len(min_endings):
        min_endings.append(t)
    else:
        min_endings[pos] = t

longest = 0
max_begins = []
for i in range(temp_num - 1, -1, -1):
    t = temps[i]
    # negative to keep the binary search happy
    pos = bisect_left(max_begins, -t)
    longest = max(longest, pref_longest[i] + pos)

    insert_pos = bisect_left(max_begins, -t - max_cheating)
    if insert_pos == len(max_begins):
        max_begins.append(-t - max_cheating)
    else:
        max_begins[insert_pos] = -t - max_cheating
print(longest)

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25