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:
def maxLenSub(arr, n, k): 
    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(arr[i] - arr[j]) <= k 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] 
      
    #required maximum length subsequence 
    return max
n,k=map(int,input().split())
A = [int(input()) for i in range(n)] 
print(maxLenSub(A, n, k))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
dp = [0] * 300000

for i in range(n):
  tmp = int(input())
  if tmp - k <= 0:
    s = 0
  else:
    s = tmp - k - 1 
  if tmp + k >= 300000:
    e = 300000
  else:
    e = tmp + k

  if tmp != 1:
  	before_max = max(dp[s:(tmp-1)])
  else:
    before_max = 0
  if tmp != 300000:
  	after_max = max(dp[tmp:e])  
  else:
    after_max = 0
  
  tmp_max = max(after_max,before_max)
  dp[tmp-1] = tmp_max + 1

ans = max(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# author:  Taichicchi
# created: 26.09.2020 21:52:45

import sys

N, K = map(int, input().split())

A = [int(input()) for _ in range(N)]

ans = 0
while N > 0:
    tmp = 1
    idx = 0
    for i in range(1, len(A)):
        if abs(A[i] - A[idx]) <= K:
            tmp += 1
            idx = i
    N -= 1
    A.pop(0)
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
a=[int(input()) for i in range(n)]
maxs=1
#lis=[]
for i in range(n-1):
    cnt=1
    j=1
    while i<=n-2:
        if abs(a[i+j]-a[i])<=k:
            #lis.append(a[i+j])
            #print(lis)
            cnt+=1
            i+=j
            j=1
        else:
            j+=1
        if j>n-i-1:
            break
    maxs=max(maxs,cnt)
print(maxs)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N, K = map(int, input().rstrip().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:
            ix2 = 2*i
            v1 = buf[ix2+1]
            v2 = buf[ix2+2]
            buf[i] = v1 if v1 > v2 else v2
            i = (i-1) // 2
    
    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
        ix2 = i*2
        c1 = _search(l, nwidth, ix2+1, q_left, q_right)
        c2 = _search(l+nwidth, nwidth, ix2+2, q_left, q_right)
        return c1 if c1 > c2 else c2
    
    for _ in range(N):
        a = int(input().rstrip())
        maxlen = _search(0, WIDTH, 0, a-K, a+K)
        update(a, maxlen+1)
    print(_search(0, WIDTH, 0, 0, 300000))

main()

Submission status: Time Limit Exceeded

Solution code:
X= input().split()
N = int(X[0])
K = int(X[1])
A = list()
ANS = list()
for i in range(N):
  Y = input()
  A.append(int(Y))
for i in range(N):
  B = list()
  for Z in range(i, N):
    if Z == i:
      B.append(A[Z])
    else:
      if abs(A[Z-1]-A[Z])<=K:
        B.append(A[Z])
  ANS.append(len(B))
print(max(ANS))

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
B = []
result = 1
for j in range(N):
  B.append(1)
  for k in range(j):
    if A[N-j-1] <= A[N-k-1] and A[N-k-1] -  A[N-j-1] <= K:
      B[j] = max(B[j], B[k] + 1)
    elif A[N-k-1] < A[N-j-1] and A[N-j-1] - A[N-k-1] <= K:
      B[j] = max(B[j], B[k] + 1)
  if B[j] >= result:
    result = B[j]
print(result)

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)


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
        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())
A = list(int(input()) for _ in range(N))

dp = [0] * (N+1)
for i, a in enumerate(A):
    tmp = [0] * (N+1)
    for j in range(i, N):
        tmp[j+1] = tmp[j]
        if abs(A[j] - A[j-1]) <= K:
            tmp[j+1] += 1
    if tmp[-1] > dp[-1]:
        dp = tmp

print(dp[-1])

Submission status: Time Limit Exceeded

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

sequence = []
for i in range(N):

    a = int(input())
    sequence.append(a)

max_length = 0
for i in range(len(sequence)):
    answer = []
    _from = i
    _to = _from + 1
    while True:
        try:
            if abs(sequence[_from] - sequence[_to]) <= K:
                answer.append(sequence[_to])
                _from = _to
                _to += 1
            else:
                _to += 1
        except Exception:
            break

    if max_length < len(answer) + 1:
        max_length = len(answer) + 1


print(max_length)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#itertools.combinations()

def Judge(li,num):
  numli=range(len(li))
  for i in range(len(li)-1):
    cli=list(itertools.combinations(numli,len(li)-i))
    for j in cli:
      a=[]
      a.clear()
      for k in j:
        a.append(li[k])
      
      if len(a)==7 and a[2]==3 and a[1]==4 and a[0]==1and a[3]==6 and a[4]==9:
        judge=True
        for j in range(len(a)-1):
          if abs(a[j]-a[j+1])>num:
            judge=False
            break
          if judge==True:
            print(len(a))
            return
        
      
    
  
lenli,num=map(int,input().split())
li=[]
for i in range(lenli):
  li.append(int(input()))
Judge(li,num)

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**3]:
        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 sys
input = lambda : sys.stdin.readline().rstrip()

n, k = map(int, input().split(" "))

M = 300000
#nums = [int(input()) for i in range(n)]
#graph = [[] for i in range(n)]
#
#for node1 in range(n-1):
#    num1 = nums[node1]
#    for node2 in range(node1+1, n):
#        num2 = nums[node2]
#        if abs(num1-num2) <= k:
#            graph[node2].append(node1)

kosuus = [0] * (M+1)

out = 0
for i in range(n):
    num = int(input())
    min_i = max(1, num-k)
    max_i = min(M-1, num+k)
    kosuu = max(kosuus[min_i:max_i+1]) + 1
    kosuus[num] = kosuu
    out = max(kosuu, out)
     
print(out)

Submission status: Time Limit Exceeded

Solution code:
# https://qiita.com/takayg1/items/c811bd07c21923d7ec69
#####segfunc#####
def segfunc(x, y):
    return max(x, y)
#################

#####ide_ele#####
ide_ele = -1

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc=segfunc, ide_ele=ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


n, k = map(int, input().split())
As = [int(input()) for i in range(n)]

max_a = max(As)

# index=iを使ったときの最長配列
seg_tree = SegTree([0 for i in range(max_a + 1)])
for i, a in enumerate(As):
    # if i == 0:
    #     seg_tree.update(a, 1)
    #     continue
    
    # As[:i]の中から[a - K, a + K] に収まる最大のindexを探す
    # print("search {} in [{}, {})", max(a - k, 0), min(a + k, max_a + 1))
    ret = seg_tree.query(max(a - k, 0), min(a + k + 1, max_a + 1))
    # print("max_value", ret)

    seg_tree.update(a, ret + 1)

    # print([seg_tree.query(j, j + 1) for j in range(max_a + 1)])

print(seg_tree.query(0, max_a + 1))


"""
# index=iを使ったときの最長配列
ans = [0 for i in range(n)]

for i, a in enumerate(As):
    if i == 0:
        ans[i] = 1
        continue

        # ans[:i]の最大値を返す s.t. As[index] in [a - K, a + K]
        ret = 
        ans[i] = ret + 1

"""

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    u = 300010
    cnt = [0] * u
    for _ in range(n):
        a = int(input())
        m = max(cnt[max(a-k,0):min(a+k,u)+1])
        cnt[a] = m+1
    print(cnt[a])

main()

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**4]:
        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
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)

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

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

    # dp[i] = i個目を取ったときの最長列長
    dp = [1] * (n)

    for i in range(1, 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(max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
def maxLenSub(arr, n, k): 
    mls=[1]*n

    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
                   
    max_val = max(mls)
    return max_val

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:
n, k = map(int, input().split())
a = [int(input()) for i in range(n)]
b = [None for i in range(n)]
b[-1] = 1
for i in range(n-2, -1, -1):
  # Highest score selecting a[i].
  b[i] = max( (b[j] for j in range(i+1, n) if a[i]-k <= a[j] <= a[i]+k), default=0) + 1
print(max(b))

Submission status: Time Limit Exceeded

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

B = [0] * len(A)
for b in range(len(B)):
  tmplist = []
  for idx, i in enumerate(range(b, len(A))):
    if idx == 0:
      tmp = A[i]
      tmplist.append(A[i])
      continue
    if abs(tmp - A[i]) <= K:
      tmplist.append(A[i])
      tmp = A[i]
  B.append(len(tmplist))
    

print(max(B))

Submission status: Time Limit Exceeded

Solution code:
#最長増加部分列問題
N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
dp=[0]*N
 
res=0
for i in range(N):
    dp[i]=1
    for j in range(i):
        if abs(A[j]-A[i])<=K:
            dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
print(res)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
ans=[1]
A_old=[int(input())]
num=1
for _ in range(N-1):
    A_new=int(input())
    for i in range(num):
        if abs(A_new-A_old[i])<=K:
            ans[i]+=1
            A_old[i]=A_new
        else:
            A_old.append(A_new)
            ans.append(1)
            num+=1

ans=max(ans)
if ans==1:
    ans=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

def main(args):
    n, k = map(int,input().split())
    
    A = []
    for i in range(n):
        a = int(input())
        A.append(a)
    
    dp = [1]*n
    ans = 0
    
    for i in range(n):
        for j in range(i):
            if abs(A[i]-A[j]) <= k and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
    
    for i in range(n):
        if ans < dp[i]:
            ans = dp[i]
            
    print(ans)
    
if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
# 1 2 3
# a, b, c = LI()


def I(): return int(sys.stdin.buffer.readline())
# a = I()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
# abc def
# a, b = LS()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
# a = S()


def IR(n): return [I() for i in range(n)]
# 2
# 1
# 2
# [1, 2]


def LIR(n): return [LI() for i in range(n)]
# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def SR(n): return [S() for i in range(n)]
# 2
# abc
# def
# [abc, def]


def LSR(n): return [LS() for i in range(n)]
# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def SRL(n): return [list(S()) for i in range(n)]
# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


n, k = LI()
a = IR(n)
ans = 0
for bit in range(1 << n):
    num = []
    flg = 1
    for i in range(n):
        if (bit >> i) & 1:
            if len(num) == 0 or abs(num[-1] - a[i]) <= k:
                num.append(a[i])
            else:
                flg = 0
                break
    if flg:
        ans = max(len(num), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n,k = ip()
x = [inp() for i in range(n)]
dp = [1]*n
for i in range(n):
    for j in range(i):
        if abs(x[i]-x[j]) <= k:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, k = map(int, input().split())
num_list = deque()

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

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

Submission status: Time Limit Exceeded

Solution code:
#D
n,k = map(int,input().split())
a = [int(input()) for i in range(n)]
Max = 0
for i in range(len(a)):
    cnt = 1
    for j in range(i+1,len(a)) :
        if abs(a[i]-a[j]) <= k:
            cnt += 1
        i = j
    if Max < cnt :
        Max = cnt
        
print(Max)

Submission status: Time Limit Exceeded

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

dp = [0]*n

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

Submission status: Time Limit Exceeded

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

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

list_B=[]
NGlist=[]
list_B.append(list_A[0])
for i in range(a-1):
    c=list_A[i]
    d=list_A[i+1]
    if(c>=d):
        if(c - d <= b):
            list_B.append(d)
        else:
            NGlist.append(i)
    else:
        if(d - c <= b):
            list_B.append(d)
        else:
            NGlist.append(i)
res=len(list_B)
#print(NGlist)

while(len(NGlist)>0):
    list_B=[]
    num=NGlist[0]
    for i in range(num,a-num-1):
        c=list_A[i]
        d=list_A[i+1]
        if(c>=d):
            if(c - d <= b):
                list_B.append(d)
                if(i in NGlist):
                    NGlist.remove(i)
        else:
            if(d - c <= b):
                list_B.append(d)
                if(i in NGlist):
                    NGlist.remove(i)
    
        if res<=len(list_B):
            res=len(list_B)
    #print(list_B)    
    NGlist.remove(num)
       
print(res)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")


N,K = LI()
A = [I() for _ in range(N)]
ans = 0

# ビット全探索
for i in range(1 << N):
    c = 0
    flag = True
    before = -1
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        if not (before == -1) and abs(before - A[j])>K:
            flag = False
            break
        before = A[j]
        c += 1
    # 全てX以上であれば更新
    if flag:
        ans = max(ans, c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = [int(input()) for x in range(N)]
L = []
Lkari = []
saityouL = [1]*N

def f(x):#最後がA[x]の部分数列の最長
    L = []
    a = []
    global saityouL
    for p in range(x):
        if abs(A[p]-A[x]) <= K:
            L += [p]#それより手前で絶対値が３以下の数字の場所

    if len(L) == 0:
        saityouL[x] = 1
        return 1
    else:
        for q in range(len(L)):
            a += [saityouL[L[q]]]
        saityouL[x] = max(a) + 1
        return max(a) + 1

for r in range(N):
    f(r)

print(max(saityouL))












"""
L = []
goukei = 0
goukeimax = 0

for p in range(N-1):
    if abs(A[p]-A[p+1]) <= K:
        L += [1]
    else:
        L += [0]

for q in range(N-1):
    if L[q] == 1:
        goukei += 1
    else:
        goukeimax = max(goukei,goukeimax)
        goukei = 0

print(goukeimax)
print(L)
"""

Submission status: Time Limit Exceeded

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

a = []
for _ in range(n):
    a.append(int(input()))
b = [a[0]]
ans = [1]
for i in range(1, n):
    for bi in range(len(b)):
        flag = False
        if abs(a[i] - b[bi]) <= k:
            ans[bi] += 1
            b[bi] = a[i]
            flag = True
            continue
        if not flag:
            b.append(a[i])
            ans.append(1)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

for j in range(N):
  for k in range(j):
    if A[N-j-1] <= A[N-k-1] and A[N-k-1] -  A[N-j-1] <= K:
      B[N-j-1] = max(B[N-j-1], B[N-k-1] + 1)
    elif A[N-k-1] < A[N-j-1] and A[N-j-1] - A[N-k-1] <= K:
      B[N-j-1] = max(B[N-j-1], B[N-k-1] + 1)
print(max(B))

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
    if a-K-1<0: l=0
    else: l=a-K-1
    if a+K-1>san-1: r=san
    else: r=a+K
    L[a-1]= max(L[l:r]) +1
    #print(L[:10])
print(max(L))

Submission status: Time Limit Exceeded

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

cnt = 1
cnt_list = []
for i in range(N):
  F = A[i]
  for j in range(i+1,N):
    num = abs(A[j]-F)
    if num <= K:
      F = A[j]
      cnt +=1
    cnt_list.append(cnt)
  cnt = 1
    
print(max(cnt_list))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
ans=[1]
A_old=[int(input())]
for _ in range(N-1):
    A_new=int(input())
    for i in range(len(A_old)):
        if abs(A_new-A_old[i])<=K:
            ans[i]+=1
            A_old[i]=A_new
        else:
            A_old.append(A_new)
            ans.append(1)

ans=max(ans)
if ans==1:
    ans=0
print(ans)

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 :
    cnt = 1
    ans = num_list[j]
    for l in range(1, n - j) :
        if abs(ans - num_list[l + j]) <= k :
            ans = num_list[l + j]
            cnt += 1
            
    max_len = max(max_len, cnt)
    j += 1
    
    
print(max_len)

Submission status: Time Limit Exceeded

Solution code:
#最長増加部分列問題
N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
dp=[0]*N

res=0
for i in range(N):
    dp[i]=1
    for j in range(i):
        if abs(A[j]-A[i])<=K:
            dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
print(res)

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):
        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 sys

n, k = map(int, input().split())

arr = []
dp = [1] * n
for _ in range(n):
    arr.append(int(sys.stdin.readline()))

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

n, k = map(int, input().split(" "))

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

for node1 in range(n-1):
    num1 = nums[node1]
    for node2 in range(node1+1, n):
        num2 = nums[node2]
        if abs(num1-num2) <= k:
            graph[node2].append(node1)

lens = []
max_ = 0
for node in range(n):
    if len(graph[node]) == 0:
        len_ = 1
    else:
        len_ = max([lens[kid] for kid in graph[node]]) + 1
    lens.append(len_)
    max_ = max(len_, max_)

print(max_)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

t = [[] for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(len(t)-1, -1, -1):
        idx = bisect_left(t[j], A[i])
        if idx != len(t[j]):
            if abs(t[j][idx] - A[i]) <= K:
                t[j+1].append(A[i])
                ans = max(ans, j+2)
                break
        elif idx > 0:
            if abs(t[j][idx-1] -A[i]) <= K:
                t[j+1].append(A[i])
                ans = max(ans, j+2)
                break
    else:
        t[0].append(A[i])
        ans = max(ans, 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def longestSubseqWithDiff(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())

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

print(longestSubseqWithDiff(a, n, k))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)

def scc(G):
    N = len(G)
    RG = [[] for _ in range(N)]
    
    for i, e in enumerate(G):
        for v in e:
            RG[v].append(i)
            
    order = []
    used = [0] * (N + 1)
    group = [None] * (N + 1)
 
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
 
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
 
    for i in range(N):
        if not used[i]:
            dfs(i)
            
    used = [0] * (N + 1)
    label = 0
    
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
            
    G0 = [set() for _ in range(label)]
    GP = [[] for _ in range(label)]
    
    for v in range(N):
        lbs = group[v]
        for w in G[v]:
            lbt = group[w]
            if lbs == lbt:
                continue
            G0[lbs].add(lbt)
        GP[lbs].append(v)
    return group, GP
 
 
class twosat():
    def __init__(self, n):
        self.n = n
        self.E = [[] for _ in range(n * 2)]
        
    def sat(self):
        group, GP = scc(self.E)
        re = [0] * self.n
        for i in range(self.n):
            if group[2 * i] == group[2 * i + 1]:
              return (0, [])
            if group[2 * i] < group[2 * i + 1]:
              re[i] = 1
        return (1, re)
 
 
n, d = map(int, input().split())
ts = twosat(n)
G = []
for _ in range(n):
    a = int(input())
    G.append(a)

for i, x1 in enumerate(G):
    for j, x2 in enumerate(G[:i]):
        if abs(x1 - x2) > d:
            ts.E[i * 2 + (1 ^ 1)].append(j * 2 + 1)
            ts.E[j * 2 + (1 ^ 1)].append(i * 2 + 1)

flg, re = ts.sat()
print(sum(re))

Submission status: Time Limit Exceeded

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

for i in range(N):
    max_value = 0
    Ai = An[i]
    for j in range(i):
        Aj = An[j]
        if abs(Ai - Aj) <= K:
            max_value = max(max_value, dp[j])
    dp[i]+=max_value

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
#k = int(input())
n,k = map(int, input().split())
#a = list(map(int, input().split()))
cnt = [0]*(3*10**5+1)

for _ in range(n):
    a = int(input())
    cnt[a] = max(cnt[max(0,a-k):min(3*10**5+1,a+k+1)])+1

print(max(cnt))

Submission status: Time Limit Exceeded

Solution code:
def scc(G):
    N = len(G)
    RG = [[] for _ in range(N)]
    
    for i, e in enumerate(G):
        for v in e:
            RG[v].append(i)
            
    order = []
    used = [0] * (N + 1)
    group = [None] * (N + 1)
 
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
 
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
 
    for i in range(N):
        if not used[i]:
            dfs(i)
            
    used = [0] * (N + 1)
    label = 0
    
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
            
    G0 = [set() for _ in range(label)]
    GP = [[] for _ in range(label)]
    
    for v in range(N):
        lbs = group[v]
        for w in G[v]:
            lbt = group[w]
            if lbs == lbt:
                continue
            G0[lbs].add(lbt)
        GP[lbs].append(v)
    return group, GP
 
 
class twosat():
    def __init__(self, n):
        self.n = n
        self.E = [[] for _ in range(n * 2)]
        
    def sat(self):
        group, GP = scc(self.E)
        re = [0] * self.n
        for i in range(self.n):
            if group[2 * i] == group[2 * i + 1]:
              return (0, [])
            if group[2 * i] < group[2 * i + 1]:
              re[i] = 1
        return (1, re)
 
 
n, d = map(int, input().split())
ts = twosat(n)
G = []
for _ in range(n):
    a = int(input())
    G.append(a)

for i, x1 in enumerate(G):
    for j, x2 in enumerate(G[:i]):
        if abs(x1 - x2) > d:
            ts.E[i * 2 + (1 ^ 1)].append(j * 2 + 1)
            ts.E[j * 2 + (1 ^ 1)].append(i * 2 + 1)

flg, re = ts.sat()
print(sum(re))

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]*(n+1)
# dp[0]=1

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