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:
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
    def __delitem__(self, idx):
        self[idx] = self._default
    def __getitem__(self, idx):
        return self.data[idx + self._size]
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
    def __len__(self):
        return self._len
    def query(self, start, stop):
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
M=600001
s=SegmentTree([0]*M)
for i in range(n):
    a=int(input())
    v=0
    if a>k:v=a-k
    s[a]=1+s.query(v,a+k+1)
print(s.query(0,M))

Submission status: Time Limit Exceeded

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

A=[]
for i in range(n):
    A.append(int(input()))



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

dp[0]=1

for i in range(1,n):
    for j in range(i):
        if -k<=(A[j]-A[i])<=k:
            dp[i]=max(dp[i],dp[j]+1)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
 
ans = []
 
i = 0
while(i<=N-1):
  a = A[i]
  T = 1
  b = i
  while (b<=N-2):
    if ( abs(a-A[b+1]) <= K ):
      T += 1
      a = A[b+1]
    else:
      T += 0
    b += 1
  ans.append(T)
  i += 1
  
print(max(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

N, K = list(map(int, input().split()))
A = [0] * N
landmark = [1] * N
for i in range(N):
    A[i] = int(input())

queue = deque()
for i in range(N - 1):
    queue.append([[i], i + 1])
while len(queue) != 0:
    now, ind = queue.popleft()
    # 探索条件
    # print("now", now, ind)
    while True:
        if ind >= N:
            break
        if abs(A[ind] - A[now[-1]]) <= K and landmark[ind] < len(now) + 1:
            queue.appendleft([copy.copy(now), ind + 1])
            now.append(ind)
            queue.appendleft([copy.copy(now), ind + 1])
            landmark[ind] = len(now)
            break
        else:
            ind += 1
print(max(landmark))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-09-26 22:28:46 +0900
# LastModified: 2020-09-26 22:37:43 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from copy import deepcopy


def main():
    N, K = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(int(input()))
    ans = 0
    for i in range(N):
        cnt = 1
        unko = deepcopy(A[i:])
#        print(unko)
        j = 1
        while j < len(unko):
            if abs(unko[j-1]-unko[j]) <= K:
                j += 1
                cnt += 1
            else:
                unko.pop(j)
        if cnt > ans:
            ans = cnt
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

n,k=map(int,input().split())
a=list(map(int,sys.stdin.read().split()))

dp=[1]*(n+10)
maxp=0
checked=[0]*(n+10)
for i in range(n):
  if checked[i]==1:
    continue
  for j in range(i+1,n):
    if abs(a[i]-a[j]) <= k:
      checked[j]==1
      if dp[j] < dp[i]+1:
        dp[j]=dp[i]+1
        if maxp < dp[j]:
          maxp=dp[j]
  
print(maxp)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
    def __delitem__(self, idx):
        self[idx] = self._default
    def __getitem__(self, idx):
        return self.data[idx + self._size]
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
    def __len__(self):
        return self._len
    def query(self, start, stop):
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
M=300001
s=SegmentTree([0]*M)
for i in range(n):
    a=int(input())
    v,w=0,M
    if a>k:v=a-k
    if a+k+1<M:w=a+k+1
    s[a]=1+s.query(v,w)
print(s.query(0,M))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 1000), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

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
c = [0]*n

for i in range(n):
  for j in range(i-1,-1,-1):
    if c[j] == 0:
      x = a[j]-a[i]
      if abs(x)<=3:
        c[j] = 1
        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 = [input() for i in range(N)]
ans = [1] * N

for j in range(N):
    if max(ans) >= N - j:
        break
    before = j
    after = j + 1
    while after < N:
        if abs(int(A[after]) - int(A[before])) <= K:
            ans[j] += 1
            before = after
            after = before +  1
        else:
            after += 1
    
print(max(ans))

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,[]] for i in range(N)}
for i in range(N):
    for j in range(i+1,N):
        if 0<=A[j]-A[i]<=K:
            G[i][1].append(j)
            G[j][0] += 1
            break
for i in range(N):
    for j in range(i+1,N):
        if 0<A[i]-A[j]<=K:
            G[i][1].append(j)
            G[j][0] += 1
            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()
        for y in G[x][1]:
            if 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:
def main():
    N,K = map(int,input().split())
    A = [int(input()) for _ in range(N)]
    dp2 = [0] * N
    max0 = 0
    for i in range(N):
        tmax = 0
        for j in range(i+1):
            if -K <= (A[i]-A[j]) <= K:
                tmax = max(tmax,dp2[j]+1)
        dp2[i] = tmax  
        max0 = max(max0,tmax)
    print(max0)
main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
    def __delitem__(self, idx):
        self[idx] = self._default
    def __getitem__(self, idx):
        return self.data[idx + self._size]
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
    def __len__(self):
        return self._len
    def query(self, start, stop):
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

import sys
z=sys.stdin.readline
n,k=map(int,z().split())
M=1048576
s=SegmentTree([0]*M)
for i in range(n):
    a=int(z())
    v,w=0,M
    if a>k:v=a-k
    if a+k+1<M:w=a+k+1
    s[a]=1+s.query(v,w)
print(s.query(0,M))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
dp = np.zeros(N)
dp[0] = 1
for i in range(1,N):
    P_ind = np.argsort(dp[:i])[::-1]
    P = np.sort(dp[:i])[::-1]
    dp[i] = 1
    for j in range(i-1):
        if abs(P[j]-A[i]) <= K:
            dp[i] = dp[P_ind[j]] + 1
            break
           
print(int(dp[N-1]))

Submission status: Time Limit Exceeded

Solution code:
import math
class SegmentTree:
    def __init__(self, operator, length, initial_val, invalid_val):
        self.operator = operator
        self.depth = math.ceil(math.log2(length))
        self.len = length
        self.memlen = 2 ** self.depth
        self.initial_val = initial_val
        self.invalid_val = invalid_val
        self.__len__ = lambda: self.length
        self.memory = [initial_val for _ in range(2*self.memlen -1)]


    def _sub_query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.invalid_val
        elif a <= l and r <= b:
            return self.memory[k]
        else:
            vl = self._sub_query(a, b, k*2+1, l, (l+r)//2)
            vr = self._sub_query(a, b, k*2+2, (l+r)//2, r)
            return self.operator(vl,vr)


    def query(self, a, b):
        a, b = max(a, 0), max(b, 0)
        a, b = min(a, self.memlen), min(b, self.memlen)
        return self._sub_query(a, b, 0, 0, self.memlen)

    def update(self, index, x):
        index += self.memlen-1
        self.memory[index] = x
        while(index):
            index = (index-1) // 2
            self.memory[index] = self.operator(self.memory[index*2+1], self.memory[index*2+2])

def main():
    n, k = map(int, input().split())
    segu = SegmentTree(max, 300000, 0, 0)
    a = int(input())
    segu.update(a-1, 1)
    for _ in range(n-1):
        a = int(input())
        query_max = segu.query(a-k, a + k +1)
        segu.update(a, query_max+1)
    print(segu.memory[0])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def solve():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    dpn = [1 for _ in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            if -K <= A[i]-A[j] <= K:
                dpn[j] = max(dpn[j], dpn[i]+1)
                    
    return max(dpn)


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
M = 300000
P = {}
for i in range(N):
  a = int(input())
  c = 0
  for j in range(max(a - K, 0), min(a + K + 1, M + 1)):
    c = max(P.get(j, 0), c)
  P[a] = max(P.get(a, 0), c + 1)
p = list(P.values())
print(max(p))

Submission status: Time Limit Exceeded

Solution code:
import sys

# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10 ** 5 + 10)

def rec(pos, a, dp, n, k):
    if dp[pos] != -1:
        return dp[pos]
    dp[pos] = 1
    for nxt in range(pos + 1, n):
        if abs(a[pos] - a[nxt]) <= k:
            dp[pos] = max(dp[pos], rec(nxt, a, dp, n, k) + 1)
    return dp[pos]


def acl_beginner_d():
    n, k = map(int, input().split())
    a = []
    for _ in range(n):
        a.append(int(input()))
    dp = [-1] * n
    ans = 0
    for i in range(n-1, -1, -1):
        v = rec(i, a, dp, n, k)
        ans = max(ans, v)
    print(ans)


acl_beginner_d()

Submission status: Time Limit Exceeded

Solution code:
N , M = map(int, input().split())
listA=[int(input()) for i in range(N)]


def LIS(L, X):
  res=0
  N = len(L)
  dp=[1]*N
  for i in range(N):
    for j in range(i):
      if abs(L[j]-L[i]) <= X:
        dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
  return res

print(LIS(listA, M))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
s =[int(input())for i in range(a)]
w =[]
t =[]
cnt = 0
count = 0
for i in range(a):
    w.clear()
    w.append(s[i])
    for j in range(i+1,a):
        if abs(w[-1] - s[j]) <=b:
            count +=1
    if count > cnt:
        cnt = count
    count =0
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
import sys
input = sys.stdin.readline
n,k = map(int,input().split())

A = [int(input()) for i in range(n)]

ng = n+1
ok = 0

def queri(b):
    dp = list([0 for _ in range(b+1)] for _ in range(n+1)) 
    j = 0
    for i in range(n):
        la = dp[i][j]
        if abs(A[i]-la) <= k:
            dp[i+1][j+1] = A[i]
            j += 1
            if j == b:
                return True
                exit()
        else:
            dp[i+1][j] = la

    if dp[-1][-1] != 0:
        return True
    else:
        return False

while ng - ok > 1:
    mid = (ok+ng)//2
    if queri(mid) :
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

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

li = [input() for _ in range(n)]

ans = 0

for bit in range(1 << n):
    lis = []
    for i in range(n):
        if bit & (1 << i):
            pass
        else:
            lis.append(int(li[i]))
    if len(lis) >= ans:
        flag = True
        for i in range(len(lis)):
            if flag:
                if i != 0:
                    if abs(lis[i] - lis[i-1]) > k:
                        flag = False
        if flag:
            ans = max(ans, len(lis))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[int(input()) for i in range(n)]
ans=[0]*n

for i in range(n-2,-1,-1):
  for j in range(i,n-1):
    tmp=0
    for m in range(j+1,n):
      t = 1 if abs(l[j]-l[m])<=k else 0
      ans[j]=t+ans[m]
      if tmp<ans[j]:break
      tmp=ans[j]
print(ans[0]+1)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
l = []
for i in range(n):
    l.append(int(input()))

root = [1]*n

for i in range(n)[-2::-1]:
    num = 0
    for j in range(i + 1, i + 500):
        if j >= n:
            break
        if abs(l[i] - l[j]) <= k:
            num = max(num, root[j])
    root[i] += num

print(max(root))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
import sys
input = sys.stdin.readline
n,k = map(int,input().split())

A = [int(input()) for i in range(n)]

ng = n+1
ok = 0

def queri(b):
    dp = list([0 for _ in range(b+1)] for _ in range(n+1)) 
    j = 0
    for i in range(n):
        la = dp[i][j]
        if abs(A[i]-la) <= k:
            dp[i+1][j+1] = A[i]
            j += 1
            if j == b:
                return True
                break
        else:
            dp[i+1][j] = la

    if dp[-1][-1] != 0:
        return True
    else:
        return False

while ng - ok > 1:
    mid = (ok+ng)//2
    if queri(mid) :
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque

def getval():
    n,k = map(int,input().split())
    a = [int(input()) for i in range(n)]
    return n,k,a 

def main(n,k,a):
    t = [0 for i in range(2**20+1)]
    ans = 0
    for i in range(n):
        cur = a[i]
        floor = max(1,cur-k)
        ceil = min(cur+k,2**19)
        q = deque([1])
        temp = 1
        #print(cur,floor,ceil)
        while q:
            idx = q.pop()
            h = math.floor(math.log2(idx))
            curfloor = (idx-2**h) * 2**(19-h) + 1
            curceil = (idx-2**h+1) * 2**(19-h)
            nextceil = ((idx*2)-2**(h+1)+1) * 2**(19-(h+1))
            nextfloor = nextceil + 1
            #print(h,idx)
            #print(idx,curfloor,curceil,nextfloor,nextceil)
            if curfloor>=floor and curceil<=ceil:
                if temp<t[idx]+1:
                    temp = t[idx] + 1
                continue
            if nextceil>=floor and h<19:
                q.append(idx*2)
            if nextfloor<=ceil and h<19:
                q.append(idx*2+1)
            #t[idx] = max(t[idx],temp)
        idx = 1
        for h in range(20):
            t[idx] = max(t[idx],temp)
            idx *= 2
            nextceil = ((idx)-2**(h+1)+1) * 2**(19-(h+1))
            #print(nextceil)
            if cur>nextceil:
                idx += 1
    print(t[1])
        #print(t[2**19+2])
        

if __name__=="__main__":
    n,k,a = getval()
    main(n,k,a)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

n,k=map(int,input().split())
a=list(map(int,sys.stdin.read().split()))

dp=[1]*(n+10)
maxp=0

for i in range(n):
  for j in range(i+1,n):
    if dp[j] < dp[i]+1 and abs(a[i]-a[j]) <= k:
      dp[j]=dp[i]+1
      if maxp < dp[j]:
        maxp=dp[j]
  
print(maxp)

Submission status: Time Limit Exceeded

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

print(max(dp2))

Submission status: Time Limit Exceeded

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

for i in range(N):
    u = A[i]+K
    l = A[i]-K
    for j in range(i+1,N):
        if l <= A[j] <= u:
            maxl[j] = max(maxl[j],maxl[i]+1)
    #print(maxl)
print(max(maxl))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]


dp = [1] * n

for i in range(n):
    for j in range(0, i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
l = list()
for _ in range(N):
  l.append(int(input()))
llen = [0]*N
for i in reversed(range(N)):
  mlen = [x[1] for x in zip(l[i+1:],llen[i+1:]) if -K <= x[0]-l[i] <= K]
  llen[i] = max(mlen)+1 if len(mlen) else 1
print(max(llen))

Submission status: Time Limit Exceeded

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

li = [input() for _ in range(n)]

ans = 0

for bit in range(1 << n):
    lis = []
    for i in range(n):
        if bit & (1 << i):
            lis.append(int(li[i]))

    if len(lis) >= ans:
        flag = True

        for i in range(len(lis)):
            if flag:
                if i != 0:
                    if abs(lis[i] - lis[i-1]) > k:
                        flag = False

        if flag:
            ans = max(ans, len(lis))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
A0 = int(input())
B = [[1,A0]]
for i in range(1,N):
    Ai = int(input())
    for j in range(len(B)):
        if abs(B[j][1] - Ai) <= K:
            B[j][0] += 1
            B[j][1] = Ai
    B.append([1,Ai])

ans = B[0][0]
for i in range(len(B)):
    ans = max(ans,B[i][0])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, k = map(int, input().split())
a = [int(input()) for i in range(n)]
d = defaultdict(int)
b = [None for i in range(n)]
for i in range(n):
  lo = a[i]-k
  hi = a[i]+k
  d[a[i]] = max((v for h,v in d.items() if lo<=h<=hi),default=0) + 1
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
M = 300000
P = [0 for k in range(M+1)]
for i in range(N):
  a = int(input())
  c = max(P[max(a - K, 0):min(a+K+1, M+1)]) + 1
  P[a] = max(P[a], c)
print(max(P))

Submission status: Time Limit Exceeded

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

for j in range(N):
    before = j
    after = j + 1
    while after < N:
        if abs(int(A[after]) - int(A[before])) <= K:
            ans[j] += 1
            before = after
            after = before +  1
        else:
            after += 1
    
print(max(ans))

Submission status: Time Limit Exceeded

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

li = [input() for _ in range(n)]

ans = 0

for bit in range(1 << n):
    lis = []
    for i in range(n):
        if bit & (1 << i):
            lis.append(int(li[i]))

    flag = True

    for i in range(len(lis)):
        if flag:
            if i != 0:
                if abs(lis[i] - lis[i-1]) > k:
                    flag = False

    if flag:
        ans = max(ans, len(lis))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

class segtree:
    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        [q_left, q_right] (閉区間) の値を集計して返します。
        """

        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k = get_nums_l()
    A = list(map(int, [input() for _ in range(n)]))


    # ある数字を末尾に取るときの最長列帳
    sg = segtree(300001, max, 0)

    for i in range(0, n):
        a = A[i]
        l = max(0, a-k)
        r = min(300000, a+k)
        v = sg.get(l, r)
        sg.update(a, v+1)

    print(sg.get(0, 300000))

main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import deque
    n, k = map(int, input().split())
    A = []
    for _ in range(n):
        A.append(int(input()))

    ans = 0
    d = deque([0])
    while len(d) > 0:
        c = 1
        start = d.popleft()
        j = 0
        while start + j < n - 1:
            if abs(A[start + j] - A[start + j + 1]) > k:
                d.append(start + j + 1)
            else:
                start += j
                j = 0
                c += 1
            j += 1
        ans = max(ans, c)

    print(ans)

resolve()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
dp = [[0] * N for _ in range(N)]
dp2 = [0] * N
for i in range(N):
    for j in range(i,N):
        if abs(A[i]-A[j]) <= K:
            dp[i][j] = 1
for i in range(N):
    tmax = 1
    for j in range(i+1):
        if dp[j][i]==1:
            tmax = max(tmax,dp2[j]+1)
    dp2[i] = tmax  

print(max(dp2))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split(' '))
nums = []
for _ in range(n):
  nums.append(int(input()))
a = [[0]]
    
for i in range(1, n):
  flag = 0
  for j in range(len(a) - 1, -1, -1):
    if flag == 0:
      for b in a[j]:
        if abs(nums[i] - nums[b]) <= k:
          flag = 1
          if j + 1 == len(a):
            a.append([i])
          else:
            a[j + 1].append(i)
          continue
  if flag == 0:
    a[0].append(i)
      
print(len(a))

Submission status: Time Limit Exceeded

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

li = [input() for _ in range(n)]

ans = 0

for bit in range(1 << n):
    lis = []
    for i in range(n):
        if bit & (1 << i):
            lis.append(int(li[i]))

    flag = True

    for i in range(len(lis)):
        if i != 0:
            if abs(lis[i] - lis[i-1]) > k:
                flag = False

    if flag:
        ans = max(ans, len(lis))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, k = map(int, input().split())
a = [int(input()) for i in range(n)]
d = defaultdict(int)
for i in range(n):
  d[a[i]] = max(d[a[i]+j] for j in range(-k, k+1)) + 1
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
l = []
for i in range(n):
    l.append(int(input()))

root = [1]*n

for i in range(n)[-2::-1]:
    num = 0
    for j in range(i + 1, n)[:i + 10**2]:
        if abs(l[i] - l[j]) <= k:
            num = max(num, root[j])
    root[i] += num

print(max(root))

Submission status: Time Limit Exceeded

Solution code:
import math

def getval():
    n,k = map(int,input().split())
    a = [int(input()) for i in range(n)]
    return n,k,a 

def main(n,k,a):
    t = [0 for i in range(2**20+1)]
    ans = 0
    for i in range(n):
        cur = a[i]
        floor = max(1,cur-k)
        ceil = min(cur+k,2**19)
        q = [1]
        temp = 1
        #print(cur,floor,ceil)
        while q:
            idx = q.pop(0)
            h = math.floor(math.log2(idx))
            curfloor = (idx-2**h) * 2**(19-h) + 1
            curceil = (idx-2**h+1) * 2**(19-h)
            nextceil = ((idx*2)-2**(h+1)+1) * 2**(19-(h+1))
            nextfloor = nextceil + 1
            #print(h,idx)
            #print(idx,curfloor,curceil,nextfloor,nextceil)
            if curfloor>=floor and curceil<=ceil:
                temp = max(temp,t[idx]+1)
                continue
            if nextceil>=floor and h<19:
                q.append(idx*2)
            if nextfloor<=ceil and h<19:
                q.append(idx*2+1)
            #t[idx] = max(t[idx],temp)
        idx = 1
        for h in range(20):
            t[idx] = max(t[idx],temp)
            idx *= 2
            nextceil = ((idx)-2**(h+1)+1) * 2**(19-(h+1))
            #print(nextceil)
            if cur>nextceil:
                idx += 1
    print(t[1])
        #print(t[2**19+2])
        

if __name__=="__main__":
    n,k,a = getval()
    main(n,k,a)