Submission #636347

#	Time	Username	Problem	Language	Result	Execution time	Memory
636347		beaconmc	Global Warming (CEOI18_glo)	Pypy 3	100 / 100	230 ms	47380 KiB

glo

from bisect import *
 
n,x = map(int, input().split())
 
arr = list(map(int, input().split()))
arrneg = [-i for i in arr]
arrneg.reverse()

dp = [0 for i in range(n)]
dp2 = [0 for i in range(n)]

 

lis = []
for j in range(len(arr)):
    i = arr[j]
    
    sus = bisect_left(lis,i)
    dp[j] = sus+1
    
    if sus==len(lis):
        lis.append(i)
    else:
        lis[sus] = i

lis = []
for j in range(len(arrneg)):
    i = arrneg[j]
    
    sus = bisect_left(lis,i)
    sussy = bisect_left(lis,i+x)
    
    dp2[j] = sussy+1
    
    if sus==len(lis):
        lis.append(i)
    else:
        lis[sus] = i

dp2.reverse()
maxi = 0

for i in range(len(dp)):
    maxi = max(maxi, dp[i]+dp2[i]-1)
print(maxi)

• 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