Problem:


Score : 400 points

Problem Statement

You are given a sequence A_1, A_2, ..., A_N and an integer K.

Print the maximum possible length of a sequence B that satisfies the following conditions:

B is a (not necessarily continuous) subsequence of A.

For each pair of adjacents elements of B, the absolute difference of the elements is at most K.

Constraints

1 \leq N \leq 300,000

0 \leq A_i \leq 300,000

0 \leq K \leq 300,000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1
A_2
:
A_N

Output

Print the answer.

Sample Input 1

10 3
1
5
4
3
8
6
9
7
2
4

Sample Output 1

7

For example, B = (1, 4, 3, 6, 9, 7, 4) satisfies the conditions.

It is a subsequence of A = (1, 5, 4, 3, 8, 6, 9, 7, 2, 4).

All of the absolute differences between two adjacent elements (|1-4|, |4-3|, |3-6|, |6-9|, |9-7|, |7-4|) are at most K = 3.



Sample input:
10 3
1
5
4
3
8
6
9
7
2
4


Sample output:
7

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
num_list = []

for i in range(n) :
    num_list.append(int(input()))

#スタート位置
max_len = 0
j = 0
while n - j > max_len :
    ans_list = [num_list[j]]
    for l in range(1, n - j) :
        if abs(ans_list[-1] - num_list[l + j]) <= k :
            ans_list.append(num_list[l + j])
            
    max_len = max(max_len, len(ans_list))
    j += 1
    
    
print(max_len)

Submission status: Time Limit Exceeded

Solution code:
import types
import bisect
N , K = map(int,input().split())
A = [int(input()) for _ in range(N)]
Ad = set(A)
Ad = list(Ad)
length = len(Ad)
Ad.sort()
d = [0 for k in range(max(A)+1)]
for i in range(N):
  a = A[i]
  p = bisect.bisect(Ad,a)
  for i in range(p):
    target = Ad[p-i-1]
    if abs(target - a) <= K:
      d[a] = max(d[target] + 1,d[a])
    else:
      break
  for i in range(length - p):
    target = Ad[p+i]
    if abs(target - a) <= K:
      d[a] = max(d[target]+1,d[a])
    else:
      break
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
G = {i:[0,[-1,-1]] for i in range(N)}
for i in range(N):
    for j in range(i+1,N):
        if A[j]>=A[i] and A[j]-A[i]<=K and G[i][1][1]<0:
            G[i][1][1]=j
            G[j][0] += 1
        if A[j]<A[i] and A[i]-A[j]<=K and G[i][1][0]<0:
            G[i][1][0]=j
            G[j][0] += 1
        if G[i][1][0]>=0 and G[i][1][1]>=0:break
S = []
for i in range(N):
    if G[i][0]==0:
        S.append(i)
dist = [-1 for _ in range(N)]
for i in S:
    que = deque([(i,0)])
    dist[i] = 0
    while que:
        x,d = que.popleft()
        y = G[x][1][0]
        if y>=0 and dist[y]<d+1:
            dist[y]=d+1
            que.append((y,d+1))
        y = G[x][1][1]
        if y>=0 and dist[y]<d+1:
            dist[y]=d+1
            que.append((y,d+1))
dmax = max(dist)
print(dmax+1)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
num_list = []

for i in range(n) :
    num_list.append(int(input()))

#スタート位置
max_len = 0
for j in range(n) :
    ans_list = [num_list[j]]
    for l in range(1, n - j) :
        if abs(ans_list[-1] - num_list[l + j]) <= k :
            ans_list.append(num_list[l + j])
            
    max_len = max(max_len, len(ans_list))
    
    if n - j <= max_len :
        break
    
print(max_len)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    a = [int(input()) for _ in range(n)]
    dp = [0]*(n)
    for i in range(n):
        maxi = 0
        for j in range(i):
            if abs(a[i]-a[j]) <= k:
                if maxi < dp[j]:
                    maxi = dp[j]
        dp[i] = maxi + 1
    print(dp[n-1])
                
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys     
import math as mt
import bisect
input=sys.stdin.readline
#t=int(input())
t=1
def ncr_util():
    inv[0]=inv[1]=1
    fact[0]=fact[1]=1
    for i in range(2,300001):
        inv[i]=(inv[i%p]*(p-p//i))%p
    for i in range(1,300001):
        inv[i]=(inv[i-1]*inv[i])%p
        fact[i]=(fact[i-1]*i)%p
def solve():
    dp=[1]*(n)
    maxi=max(l[:])
    mini=min(l[:])
    d={}
    for i in range(n):
        maxm=0
        for j in range(l[i],min(maxi+1,l[i]+k+1)):
            if d.get(j,-1)!=-1:
                maxm=max(maxm,dp[d[j]])
        for j in range(max(l[i]-k,0),l[i]+1):
            if d.get(j,-1)!=-1:
                maxm=max(maxm,dp[d[j]])
            
        d[l[i]]=i
        dp[i]+=maxm
    return dp[n-1]            
       
for _ in range(t):
    #n=int(input())
    n,k=(map(int,input().split()))
    l=[]
    for i in range(n):
        l.append(int(input()))
    #n1=n
    #a=int(input())
    #b=int(input())
    #a,b,c,r=map(int,input().split())
    #x2,y2=map(int,input().split())
    
    #n=int(input())
    #s=input()
    #s1=input()
    #p=input()
    #l=list(map(int,input().split()))
    #l2=list(map(int,input().split()))
    #l=str(n)
    #l.sort(reverse=True)
    #l2.sort(reverse=True)
    #l1.sort(reverse=True)
    print(solve())

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
from bisect import bisect
n, k = list(map(int, input().split()))
al = [0] * n
for i in range(n):
    al[i] = int(input())

d = defaultdict(lambda: 0)
d[al[0]] = 1
for a in al[1:]:
    m = 0
    for i in range(max(0, a-k), a+k+1):
        m = max(m, d[i])
    d[a] = m+1
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
B = [0]*N
B[0] = 1
A = []
A.append(int(input()))
for i in range(1, N):
    a = int(input())
    A.append(a)
    for j in range(i):
        if abs(A[j]-a) <= K:
            B[i] = max(B[i], B[j]+1)
print(max(B))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list()
for i in range (N):
    a = int(input())
    A.append(a)
c = 0
for i in range (N):
    b = 1
    s = A[0]
    a = 1
    for i in range (len(A) - 1):
        if abs(s - A[a]) <= K:
            s = A[a]
            b = b + 1
        a = a + 1
    del A[0]
    if c<b:
        c = b
    if c > len(A):
        break
print(c)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(i) for i in input().split()]
AS = [int(input()) for _ in range(N)]

t = [[AS[0]]]

for i in range(1, N):
  l = t[i-1]
  if abs(l[-1] - AS[i]) <= K:
    t.append([*t[i-1], AS[i]])
  else:
    t.append(t[i-1])

print(len(t[N-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    
    BL = (300000).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
    
    buf = [0] * BUFSIZE
    
    def update(i, x):
        i += BASE
        buf[i] = x
        i = (i-1) // 2
        while i >= 0:
            v1 = buf[2*i+1]
            v2 = buf[2*i+2]
            buf[i] = v1 if v1 > v2 else v2
            i = (i-1) // 2
    
    # [q_left, q_right]
    def search(q_left, q_right):
        return _search(0, WIDTH, 0, q_left, q_right)
    
    def _search(l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return 0
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = _search(l, nwidth, 2*i+1, q_left, q_right)
        c2 = _search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return c1 if c1 > c2 else c2
    
    for _ in range(N):
        a = int(input().rstrip())
        maxlen = search(a-K, a+K)
        update(a, maxlen+1)
    print(search(0, 300000))

main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
b=[int(input()) for _ in range(n)]
dp=[0]*(max(b)+1)
c=max(b)
for i in range(n):
    dp[b[i]]=max(dp[b[i]],max(dp[max(0,b[i]-k):min(c+1,b[i]+k+1)])+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
dp = [1] * (N+1)
A = [0, int(input())]
for i in range(2, N+1):
    A.append(int(input()))
    t = 0
    for j in range(i-1, 0, -1):
        if abs(A[j] - A[i]) <= K:
            t = max(t, dp[j])
    dp[i] = t + 1

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
low = [0]*(10**5 * 3 + 1) #iで終わる長さ
for i in range(n):
    a = int(input())
    low[a] = max(low[max(0,a-k):a+k+1]) + 1
ans = max(low)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
dp = [1 for _ in range(n)]
for i in range(n):
    for j in range(i-1, -1, -1):
        if abs(a[i] - a[j]) <= k:
            dp[i] = max(dp[i], dp[j]+1)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
dp = [1 for _ in range(n)]
for i in range(n):
    for j in range(i-1, -1, -1):
        if abs(a[i] - a[j]) <= k:
            dp[i] = max(dp[i], dp[j]+1)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
def solve(N,A,K):
    dp=[1]*N
    longest=0
    for i in range(N):
        for j in range(i):
            if abs(A[i]-A[j])<=3:
                dp[i]=max(dp[i],dp[j]+1)
                longest=max(longest,dp[i])
    return longest

N,K=readMap()
A=[]
for _ in range(N):
    A.append(readInt())
print(solve(N,A,K))

Submission status: Time Limit Exceeded

Solution code:
import math
n,m=[int(i) for i in input().split()]
l=[]
for i in range(n):
    l.append(int(input()))
mls=[] 
max = 0

            #Initialize mls[] values for all indexes 
for i in range(n): 
    mls.append(1) 

            #Compute optimized maximum length subsequence 
            # values in bottom up manner 
for i in range(n): 
    for j in range(i): 
        if (abs(l[i] - l[j]) <= m and mls[i] < mls[j] + 1): 
                mls[i] = mls[j] + 1

            # Store maximum of all 'mls' values in 'max' 
for i in range(n): 
    if (max < mls[i]): 
        max = mls[i] 
#Driver program to test above 
print(max)

#This code is contributed by "Abhishek Sharma 44"

Submission status: Time Limit Exceeded

Solution code:
#d
n,k=map(int,input().split())
a=[]
for i in range(n):
    ai=int(input())
    a.append(ai)
ans=0
for i in range(2**n):
    f=0
    ansi=1
    for j in range(n):
        if ((i>>j) & 1):
            if f==1:
                if abs(g-a[j])<=k:
                    g=a[j]
                    ansi+=1
            else:
                g=a[j]
                f=1
    ans=max(ans,ansi)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [input() for i in range(N)]
ans = [0] * N
for j in range(N - 1):
    for k in range(N - j - 1):
        if abs(int(A[j + 1]) - int(A[k])) <= K:
            ans[j] += 1
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [
  int(input()) for _ in range(N)
]

lst = [0] * 300002

for i in range(N):
  a = A[i]
  min_a = max(1, a - K)
  max_a = min(300000, a + K)
  max_val = max(lst[min_a:max_a+1])
  lst[a] = max_val + 1
  
  #print(min_a, max_a)
  
print(max(lst))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(input()) for i in range(n)]
ans = 0
for i in range(n):
    x = [a[i]]
    cnt = 1
    if n-i+1 <= ans:
        break
    for j in range(i+1, n):
        if abs(x[-1]-a[j]) <= k:
            x.append(a[j])
            cnt += 1
    ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list()
for i in range (N):
    a = int(input())
    A.append(a)
c = 0
for i in range (N):
    b = 1
    s = A[0]
    a = 1
    for i in range (len(A) - 1):
        if abs(s - A[a]) <= K:
            s = A[a]
            b = b + 1
        
        a = a + 1
    del A[0]
    if c<b:
        c = b
print(c)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
dic = {}

for i in range(n):
  tmp = int(input())
  if i == 0:
    dic[tmp] = 1
  else:
    tmp_dict = dict(filter(lambda item: abs(item[1] - tmp) <= k, dic.items()))
    if tmp_dict == {}:
      dic[tmp] = 1
    else:
      tmp_max = max(tmp_dict.values())
      dic[tmp] = tmp_max + 1
ans = max(dic.values())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def maxLenSub(arr, n, k): 
    mls=[1 for i in range(n)] 
    max = 0

    for i in range(n): 
        for j in range(i): 
            if (abs(arr[i] - arr[j]) <= k and mls[i] < mls[j] + 1): 
                mls[i] = mls[j] + 1
                   
    for i in range(n): 
        if (max < mls[i]): 
            max = mls[i] 
      
    return max

n, k = map(int, input().split())
arr = []
for i in range(n):
    x = int(input())
    arr.append(x)


print(maxLenSub(arr, n, k))

Submission status: Time Limit Exceeded

Solution code:
san = 300000
N,K = [int(a) for a in input().split()]
l = [0]*300000
for _ in range(N):
    a = int(input())
    M = 0
    for i in range(-K,K+1):
        if a+i>=0 and a+i<san: M= max(M,l[a+i-1])
    l[a-1]= M+1
    #print(l[:10])
print(max(l))

Submission status: Time Limit Exceeded

Solution code:
line= input().split(" ")
a=int(line[0])
b=int(line[1])
list_A=[]
res=0

for i in range(a):
    temp=int(input())
    list_A.append(temp)

for i in range(a):
    list_B=[]
    list_B.append(list_A[i])
    for j in range(a-i-1):
        c=list_A[j]
        d=list_A[j+1]
        if(c>=d):
            if(c - d <= b):
                list_B.append(d)
        else:
            if(d - c <= b):
                list_B.append(d)

    if(len(list_B)>=res):
        res=len(list_B)
        
print(res)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys

    input = sys.stdin.readline

    n, k = [int(x) for x in input().rstrip().split(" ")]

    ans = 0
    # 最後の数字->最長数列の長さ
    len_dict = {}
    for i in range(n):
        a = int(input().rstrip())
        max_new_len = 1  # このaから開始するパターン

        # 既存のbからつなげるパターン
        for num in range(a - k, a + k + 1):
            if num in len_dict:
                new_len = len_dict[num] + 1
                if max_new_len < new_len:
                    max_new_len = new_len

        len_dict[a] = max_new_len
        ans = ans if max_new_len < ans else max_new_len

    # 集計
    print(ans)





if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = []
for i in range (0, N):
    A.append(int(input()))

def longest_subseq(n, k, a): 
    
    # Creating a list with all 0's of size equal to the length of string 
    dp = [0] * n 
      
    # Supporting list with  
    # all 0's of size 26 since  
    # the given string consists  
    # of only lower case alphabets 
    max_length = [0] * 300001
  
    for i in range(n): 
  
        # Converting the ascii value to list indices 
        curr = a[i] 
        # Determining the lower bound 
        lower = max(0, curr - k) 
        # Determining the upper bound 
        upper = min(300000, curr + k) 
        # Filling the dp array with values 
        for j in range(lower, upper + 1): 
            dp[i] = max(dp[i], max_length[j]+1) 
        # Filling the max_length array with max 
        # length of subsequence till now 
        max_length[curr] = max(dp[i], max_length[curr]) 
  
    # return the max length of subsequence 
    return max(dp) 

print(longest_subseq(N, K, A))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
numl = [0]*n
lenl = [0] * n
for i in range(n):
    numl[i] = int(input())
    temp = 0
    for j in range(0, i):
        if(abs(numl[j] - numl[i])<=k ):
            if(lenl[j] > temp):
                temp = lenl[j]
    lenl[i] = temp+1
print(max(lenl))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
an_max = 1
li = []

for t  in range(N):
    li.append(int(input()))

for t in range(N):
 a = li[t]
 an = 1

 for i in range(t+1,N):
    x = li[i]

    if abs(a - x) <= K:
        an += 1
        a = x

 if an_max < an:
     an_max = an

print(an_max)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
dp=[0]*N
dp[0]=1
Ma=max(A)
B=[0]*(Ma+1)
B[A[0]]=1
for i in range(1,N):
    a=A[i]
    Max=max(B[max(0,a-K):min(Ma+1,a+K+1)])
    dp[i]=Max+1
    B[a]=Max+1
print(max(B))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = []
for _ in range(n):
    A.append(int(input()))
    
B = [1] * (n-1)
for i in range(n-1):
    x = A[i]
    for y in A[i+1:]:
        if abs(x-y) <= k:
            B[i]+=1
            x = y
print(max(max(B), 1))

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(n) for n in input().split(" ")]
A = []
for _ in range(N):
    A.append(int(input()))


D = []

ANS = -1

for n in range(N):
    maxd = -1
    for j in range(n - 1, -1, -1):
        if j + 1 <= maxd - 1:
            break
        if A[j] >= A[n] - K and A[j] <= A[n] + K:
            d = D[j] + 1
            if maxd <= d:
                maxd = d
    if maxd == -1:
        maxd = 1
    D.append(maxd)

    if ANS <= maxd:
        ANS = maxd

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = []
t = []

for i in range(n):
    b = int(input())
    a.append(b)

for i in range(n):
    cnt = 0
    b = a[i]
    for s in range(i,n):
        if((abs(a[s] - b)) <= k):
            cnt += 1
            b = a[s]
    
    t.append(cnt)

print(max(t))

Submission status: Time Limit Exceeded

Solution code:
def get(lo, hi, idx, qs, qe):
  if hi < qs or qe < lo:
    return 0
  if qs <= lo and hi <= qe:
    return tree[idx]

  mid = (lo + hi) >> 1
  right = (idx + 1) << 1
  return max(get(lo, mid, right - 1, qs, qe), get(mid + 1, hi, right, qs, qe))

def update(lo, hi, idx, ui, val):
  if ui < lo or hi < ui:
    return
  if lo == hi:
    tree[idx] = val
    return

  mid = (lo + hi) >> 1
  right = (idx + 1) << 1
  update(lo, mid, right - 1, ui, val)
  update(mid + 1, hi, right, ui, val)
  tree[idx] = max(tree[right - 1], tree[right])

n, k = map(int, input().split())
a = []
m = 0
for i in range(n):
  a.append(int(input()))
  m = max(m, a[-1])

m = m + 1

tree = [0] * (5 * m)
for i in range(n)[::-1]:
  lo = max(0, a[i] - k)
  hi = min(m - 1, a[i] + k)
  c = get(0, m - 1, 0, lo, hi)
  # print(a[i], '->', c)
  update(0, m - 1, 0, a[i], c + 1)
  # print(tree[0])
  # print(tree[1:3])
  # print(tree[3:7])
  # print(tree[7:15])
  # print(tree[15:31])

print(get(0, m - 1, 0, 0, m - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys     
import math as mt
import bisect
input=sys.stdin.readline
#t=int(input())
t=1
def ncr_util():
    inv[0]=inv[1]=1
    fact[0]=fact[1]=1
    for i in range(2,300001):
        inv[i]=(inv[i%p]*(p-p//i))%p
    for i in range(1,300001):
        inv[i]=(inv[i-1]*inv[i])%p
        fact[i]=(fact[i-1]*i)%p
def solve():
    dp=[1]*(n)
    
    for i in range(n):
        maxi=0
        for j in range(i):
            
            if abs(l[i]-l[j])<=k:
                maxi=max(dp[j],maxi)
        dp[i]+=maxi  
    #print(dp,l,k)      
    return dp[n-1]            
       
for _ in range(t):
    #n=int(input())
    n,k=(map(int,input().split()))
    l=[]
    for i in range(n):
        l.append(int(input()))
    #n1=n
    #a=int(input())
    #b=int(input())
    #a,b,c,r=map(int,input().split())
    #x2,y2=map(int,input().split())
    
    #n=int(input())
    #s=input()
    #s1=input()
    #p=input()
    #l=list(map(int,input().split()))
    #l2=list(map(int,input().split()))
    #l=str(n)
    #l.sort(reverse=True)
    #l2.sort(reverse=True)
    #l1.sort(reverse=True)
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(input()) for i in range(n)]
ans = 0
for i in range(n):
    x = [a[i]]
    cnt = 1
    for j in range(i+1, n):
        if abs(x[-1]-a[j]) <= k:
            x.append(a[j])
            cnt += 1
    ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
dp = defaultdict(int)
for a in A:
    for prev in list(dp.keys()):
        if abs(prev - a) <= K:
            dp[a] = max(dp[prev] + 1, dp[a])
    dp[a] = max(1, dp[a])
print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split()) 
arr=[] 
for i in range(n):
    arr.append(int(input())) 
dp=[1]*n 
for i in range(1,n):
    for j in range(0,i):
        if abs(arr[i]-arr[j])<=k and dp[i]<dp[j]+1:
            dp[i]=dp[j]+1 
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
l = []
cnt = 1
ans = 1
for i in range(n):
  l.append(int(input()))
for i in range(n):
  a = l[i]
  cnt = 1
  for j in range(i+1,n-i):
    if abs(l[j] - a) <= 3:
      a = l[j]
      cnt += 1
  ans = max(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
b=[int(input()) for _ in range(n)]
dp=[[0]*(max(b)+1) for _ in range(n+1)]
a=b[0]
dp[1][a]=1
c=max(b)
for i in range(2,n+1):
    a=b[i-1]
    dp[i][a]=max(dp[i][a],1)
    for j in range(max(a-k,0),min(a+k,c+1)):
        if dp[i-1][j]!=0:
            dp[i][a-(a-j)]=max(dp[i-1][a-(a-j)],dp[i-1][j]+1)
    for j in range(c+1):
        dp[i][j]=max(dp[i][j],dp[i-1][j])
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int, input().split())


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def get(self, k):
        return self.query(k,k+1)
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res



dp=[0]*N

for i in range(N):
    a=int(input())
    if i==0:
        dp[i]=a
    else:
        def segfunc(A,B):
            A=A*(abs(a-A)<=K)
            B=B*(abs(a-B)<=K)
            return max(A,B)
        seg=SegmentTree(dp, segfunc, 0)
        now=seg.query(0,i+1)
        dp[i]=now+1

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# SHRI GANESHA    author: Kunal Verma#

import os,sys
from collections import defaultdict
from io import BytesIO, IOBase




def main():
    n,k = map(int,input().split())
    a=[int(input()) for x in range(n)]
    dp=[1 for i in range(n)]
    x=defaultdict(lambda :0)


    for i in range(n):
        down = max(a[i]-k,0)
        up = a[i]+k
        for j in range(down,up+1):
            dp[i]=max(dp[i],x[j]+1)
        x[a[i]]=max(dp[i],x[a[i]])
    print(max(dp))



BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
import sys
input = sys.stdin.readline

# 初期化最大値
INF = 0

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[-INF, -1] for _ in range(2*self.N-1)]
    
    # O(N)で初期化
    def compose(self, A):
        for k, a in enumerate(A):
            self.data[k+self.N-1] = [a, k]
        first = self.N - 1
        while first > 0:
            first = (first-1)//2
            for k in range(first, 2*first+1):
                if self.data[2*k+1][0] > self.data[2*k+2][0]:
                    self.data[k] = self.data[2*k+1][:]
                else:
                    self.data[k] = self.data[2*k+2][:]

    # k番目の値(0-indexed)をaに変更
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] > self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    # [l, r)
    # kがNodeの番号、対応する区間が[a, b)
    def query_max(self, l, r):
        if l+1 == r:
            return self.data[l+self.N-1]
        L = l + self.N
        R = r + self.N
        s = [-INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] < self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] < self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

MAX = 3*10**5+5

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

ST = SegmentTree(MAX)
# dp = [0]*(N+1)
ans = 0
for i, a in enumerate(A):
    maxscore = ST.query_max(max(a-K, 0), min(a+K+1, MAX))[0]
    # dp[i+1] = dp[max(maxind, 0)] + 1
    ans = max(maxscore+1, ans)
    ST.update(a, maxscore+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(i) for i in input().split()]
AS = [int(input()) for _ in range(N)]

ss = [[0]]

for i in range(N):
  a = AS[i]
  for s in ss:
    p = AS[s[-1]]
    if abs(a - p) <= K:
      s.append(i)
    else:
      ss.append([i])


print(max([len(s)-1 for s in ss]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    num_max = 3 * 10 ** 5 + 1
    numbers = np.zeros(num_max, dtype=np.int64)
    for _ in range(N):
        a = int(input())
        numbers[a] += 1

    ans = 0
    for index, num in enumerate(numbers):
        if num == 0:
            continue
        ans = max(numbers[index - K:index + K].sum(), ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    
    BL = (300000).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
    
    # TODO: default value
    buf = [0] * BUFSIZE
    
    def update(i, x):
        i += BASE
        buf[i] = x
        i = (i-1) // 2
        while i >= 0:
            buf[i] = compare(buf[2*i+1], buf[2*i+2])
            i = (i-1) // 2
    
    # [q_left, q_right]
    def search(q_left, q_right):
        return _search(0, WIDTH, 0, q_left, q_right)
    
    def _search(l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return 0
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = _search(l, nwidth, 2*i+1, q_left, q_right)
        c2 = _search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return compare(c1, c2)
    
    def compare(i1, i2):
        if i1 > i2:
            return i1
        else:
            return i2
    
    for _ in range(N):
        a = int(input().rstrip())
        maxlen = search(a-K, a+K)
        update(a, maxlen+1)
    print(search(0, 300000))

main()

Submission status: Time Limit Exceeded

Solution code:
class SEGTree:
    def __init__(self,n,op,e):
        self.Unit=e
        self.Op=op
        i=1<<(n.bit_length()-1)
        if i!=n:
            i*=2
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]=x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=self.Op(self.SEG[i*2+1],self.SEG[i*2+2])
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return self.Op(c1,c2)
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)

INF=10**30
N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
M=max(A)
SEG=SEGTree(M+1,max,0)

ans=0
for i in range(N):
    l=max(0,A[i]-K)
    r=min(M,A[i]+K)
    res=SEG.get(l,r+1)
    ans=max(ans,res+1)
    if SEG.get(A[i],A[i]+1)<res+1:
        SEG.update(A[i],res+1)
print(ans)