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: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele= 0 #単位元
        self.num=2**(self.n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        #return a+b #0
        #return a*b #1
        #return gcd(a,b) #0
        return max(a,b) #0か-1か-10**10 (十分小さいもの，計算に使う場合0)
        #return min(a,b) #10**10 (十分大きいもの)
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): #O(logN)
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n, k = map(int,input().split())
    A = [int(input())for _ in range(n)]
    max_a = max(A)
    A_len = [0] * (max_a + 1) # 最後の数字がiのときの最大長さ
    SEG = seg(A_len)
    for a in A:
        SEG.update(a, SEG.query(max(a - k, 1), min(a + k, n) + 1) + 1)
    print(SEG.query(1, max_a))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
count = 0
for i in range(n):
  a = int(input())
  if i == 0:
    prev = a
  if abs(a - prev) <= k:
    if count == 0:
      if i != 0:
        count += 2
        prev = a
    else:
      prev = a
      count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n, k =map(int,input().split())
a=[]
ans = 0
cnt = 1
for i in range(n):
    a.append(int(input()))

b = a[0]
for j in range(1,n):
    if abs(b-a[j]) <= k:
        b = a[j]
        cnt += 1
else:
    ans=max(ans,cnt)


print(ans)

Submission status: Wrong Answer

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

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

  t=int(input())
  if i==0:
    b.append(t)
  else:
    if abs(b[-1]-t)<=k:
      b.append(t)
print(len(b))

Submission status: Wrong Answer

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_maxflow_code = """
from __future__ import annotations

from typing import NamedTuple, Optional, List


class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int

    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = e.rev
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        e.rev.cap = new_flow

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = sum(e.cap for e in self._g[s])

        current_edge = [0] * self._n
        level = [0] * self._n

        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value

        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False

        def dfs(lim: int) -> int:
            stack = []
            edge_stack = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = e.rev
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0

        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow

    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited
"""

atcoder.maxflow = types.ModuleType('atcoder.maxflow')
exec(_atcoder_maxflow_code, atcoder.maxflow.__dict__)
MFGraph = atcoder.maxflow.MFGraph

#!/usr/bin/env python3

# from atcoder.maxflow import MFGraph
#import
#import math
#import numpy as np
#= int(input())
#= input()
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

g = MFGraph(N + 4)
ss = N + 2; tt = N + 3
s = N; t = N + 1

for i in range(N):
    g.add_edge(s, i, 1)
    g.add_edge(i, t, 1)

for i in range(N - 1):
    for j in range(i + 1, N):
        if abs(A[i] - A[j]) <= K:
            g.add_edge(i, j, 1)
            break

g.flow(s, t)

print(len(g.edges()) - 2 * N - 2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
N,K = map(int,input().split())
A = list()
for i in range (N):
    a = int(input())
    A.append(a)
c = 0
k = list()
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
            if A[0] in k:
                print(c)
                sys.exit()
            k.append(A[a])
        a = a + 1
    del A[0]
    if c<b:
        c = b
    if c >= len(A):
        break
print(c)

Submission status: Wrong Answer

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

C = 0
c = 0

for i in range(n):
  if abs(a[i]-a[i-1]) <= k:
    c += 1
  else:
    C = max(C,c)
    c = 0
    
print(C)

Submission status: Wrong Answer

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

    neg = 0
    for i in range(1, n):
        if abs(A[i - 1] - A[i]) > k:
            neg += 1
    print(n - neg)

resolve()

Submission status: Wrong Answer

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

T = 1
ans = []

i = 0
while(i<=N-2):
  a = A[i]
  while (i<=N-2):
    if ( abs(a-A[i]) <= K ):
      T += 1
      a = A[i]
    i += 1
  ans.append(T)
  i += 1
  
print(max(ans))

Submission status: Wrong Answer

Solution code:

#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
def segfunc(x, y):
    return max(x,y)
#################

#####ide_ele初期値#####
ide_ele = 0
#################

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, 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())
A = [int(input())-1 for _ in range(N)]
seg = SegTree([0 for i in range(300000)], segfunc, ide_ele)

for i in range(N):
    under = max(0,A[i]-K)
    upper = min(299999,A[i]+K)
    now = seg.query(under, upper+1)
    seg.update(A[i], now+1)

print(seg.query(0, 300000))

Submission status: Wrong Answer

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(ans-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].insert(bisect_left(t[j + 1], A[i]), A[i])
                ans = max(ans, j+2)
                break
        elif idx > 0:
            if abs(t[j][idx-1] - A[i]) <= K:
                t[j + 1].insert(bisect_left(t[j + 1], A[i]), A[i])
                ans = max(ans, j+2)
                break
    else:
        t[0].append(A[i])
        ans = max(ans, 1)

print(ans)

Submission status: Wrong Answer

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

import bisect

LIS = [seq[0]]
for i in range(1, len(seq)):
    if (LIS[-1] - K) <= seq[i] <= (LIS[-1] + K):
        LIS.append(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i]) - 1] = seq[i]
    #print(LIS, i)
print(len(LIS))

Submission status: Wrong Answer

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

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

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

print(max(t))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")

MOD = 1000000007
class Combination(object):
    def __init__(self, N):
        self.fac = [0] * (N + 1)
        self.inv = [0] * (N + 1)
        self.finv = [0] * (N + 1)
        self.fac[0] = 1
        self.finv[0] = 1
        if N > 0:
            self.fac[1] = 1
            self.inv[1] = 1
            self.finv[1] = 1
 
        # 前計算
        for i in range(2, N + 1):
            self.fac[i] = self.fac[i - 1] * i % MOD
            self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
    def com(self, N, k):
        return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


# 処理内容
def main():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]

    dp = [0] * N
    dp[0] = 1
    for i in range(N-1):
        if abs(A[i+1]-A[i]) <= K:
            dp[i+1] = dp[i] + 1
        else:
            dp[i+1] = dp[i]
    
    print(dp[N-1])
        


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

l = [a[0]]
cnt = 1
for i in range(1, n):
    for j in range(len(l)):
        if abs(l[j] - a[i]) <= k:
            cnt += 1
            l = [a[i]]
            break


print(cnt)

Submission status: Wrong Answer

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)and(a-NGlist[0]>res):
    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: Wrong Answer

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

Submission status: Wrong Answer

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(ans-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].insert(idx, A[i])
                ans = max(ans, j+2)
                break
        elif idx > 0:
            if abs(t[j][idx-1] - A[i]) <= K:
                t[j+1].insert(idx, A[i])
                ans = max(ans, j+2)
                break
    else:
        t[0].append(A[i])
        ans = max(ans, 1)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = []
for _ in range(N):
    A.append(int(input())) 
ans = 1
X = 0
for i in range(X,N-1):
  if A[i]-A[i+1] >= -K and A[i]-A[i+1] <= K:
    X = i
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

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

s=[0]*n
a=[0]*n
for i in range(n):
    a[i]=int(input())
    for ii in range(i):
        if abs(a[i]-a[ii])<=k:
            s[i]=max(s[i],s[ii]+1)
            
print(max(s))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_list = [int(input()) for i in range(N)]
count = 1
first = 0
for i in range(N):
  for j in range(first+1, N):
    if abs(A_list[first]-A_list[j])<=K:
      count+=1
      first=j
      break
print(count)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
ans = 1
nums = [l[0]]
cnts = [1]
for i in range(1, N):
  flag = True
  for j in range(len(nums)):
    if abs(l[i]-nums[j]) <= K:
      nums[j] = l[i]
      cnts[j] += 1
      flag = False
  if flag:
    nums.append(l[i])
    cnts.append(1)
print(max(cnts))

Submission status: Wrong Answer

Solution code:
class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [0] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

N,K = map(int,input().split())
ST = SegTree(300030)
for i in range(N):
    A = 300000
    l = max(0,A-K)+1
    r = min(A+K,300000)+2
    M = ST.fold(l,r)
    ST.set_val(A+1,M+1)
print(ST.X[1])

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,K = I()
A = [i() for _ in range(N)]
d = []
for i in range(N-1):
    d.append(A[i+1]-A[i])
p = 0
ans = 0
for i in range(N-1):
    if p != 0:
        p -= 1
        continue
    ans += 1
    if abs(d[i]) > K:
        n = d[i]
        for j in range(i+1,N-1-i):
            p += 1
            n += d[j]
            if abs(n) <= K:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_maxflow_code = """
from __future__ import annotations

from typing import NamedTuple, Optional, List


class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int

    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = e.rev
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        e.rev.cap = new_flow

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = sum(e.cap for e in self._g[s])

        current_edge = [0] * self._n
        level = [0] * self._n

        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value

        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False

        def dfs(lim: int) -> int:
            stack = []
            edge_stack = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = e.rev
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0

        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow

    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited
"""

atcoder.maxflow = types.ModuleType('atcoder.maxflow')
exec(_atcoder_maxflow_code, atcoder.maxflow.__dict__)
MFGraph = atcoder.maxflow.MFGraph

#!/usr/bin/env python3

# from atcoder.maxflow import MFGraph
#import
#import math
#import numpy as np
#= int(input())
#= input()
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

g = MFGraph(N + 4)
ss = N + 2; tt = N + 3
s = N; t = N + 1

for i in range(N):
    g.add_edge(s, i, 1)
    g.add_edge(i, t, 1)

for i in range(N - 1):
    for j in range(i + 1, N):
        if abs(A[i] - A[j]) <= K:
            g.add_edge(i, j, i)
            break

g.flow(s, t)

print(len(g.edges()) - 2 * N - 2)

Submission status: Wrong Answer

Solution code:
# cook your dish here
s=[int(i) for i in input().strip().split()]
n=s[0]
k=s[1]

l=[int(input()) for i in range(0,n)]
p=[]
#print(l)
for i in range(0,n-1):
    #print(abs(l[i+1]-l[i]))
    if(abs(l[i+1]-l[i])<=k):
        
        p.append(l[i+1])

if(len(p)==0):
    print(0)
else:
    print(len(p)+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
def rec(pos, a, dp, n, k):
    if dp[pos] != -1:
        return dp[pos]
    for nxt in range(pos + 1, n):
        if abs(a[pos] - a[nxt]) <= k:
            dp[pos] = rec(nxt, a, dp, n, k) + 1
            return dp[pos]
    dp[pos] = 1
    return 1


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):
        v = rec(i, a, dp, n, k)
        ans = max(ans, v)
    print(ans)


acl_beginner_d()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
ans=0
inf=10**6
temp=[[]]
a=int(input())
temp[0].append(a)
flag=True

for i in range(1,N):
    a=int(input())
    for s in temp:
        if abs(s[-1]-a)<=K:
            s.append(a)
            flag=False
    if flag:
        temp.append([a])
        flag=True


for s in temp:
    ans=max(ans,len(s))

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
ans = 1
nums = [l[0]]
cnts = [1]
for i in range(1, N):
  flag = True
  for j in range(len(nums)):
    if abs(l[i]-nums[j]) <= K:
      nums[j] = l[i]
      cnts[j] += 1
      flag = False
      break
  if flag:
    nums.append(l[i])
    cnts.append(1)
print(max(cnts))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, K = [int(i) for i in input().split()]
AS = [int(input()) for _ in range(N)]
 
ss = deque([deque([0])])
 
for i in range(N):
  a = AS[i]
  f = False
  for s in ss:
    p = AS[s[-1]]
    if abs(a - p) <= K:
      s.append(i)
    else:
      f = True
 
  if f:
    ss.append(deque([i]))
 
 
f0 = ss.popleft()
print(max([len(f0)-1, *[len(s) for s in ss]]))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[int(input())for i in range(n)]
t=[-1 for i in range(n)]
for i in range(n)[::-1]:
    j=i
    if t[i]==-1:
        e=1
        while i+1<n:
            if abs(l[i]-l[i+1])<=k:
                if t[i+1]!=-1:
                    e+=t[i+1]
                    break
                e+=1
            i+=1
        t[j]=e
print(max(t))
#print(*t)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,K = I()
A = [i() for _ in range(N)]
d = []
for i in range(N-1):
    d.append(A[i+1]-A[i])
p = 0
ans = 0
print(d)
for i in range(N-1):
    if p != 0:
        p -= 1
        continue
    ans += 1
    if abs(d[i]) > K:
        n = d[i]
        for j in range(i+1,N-1-i):
            p += 1
            n += d[j]
            if abs(n) <= K:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
count = 0
for i in range(n):
  a = int(input())
  if i == 0:
    prev = a
  if abs(a - prev) <= k:
    if count == 0:
      if i != 0:
        count += 2
        #print(a, prev, end =" ")
    else:
      count += 1
      #print(a, end =" ")
    prev = a

print(count)

Submission status: Wrong Answer

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

index = []
for i in range(n - 1):
    if abs(a[i] - a[i + 1]) > k:
        index.append(i)
cnt = 0
for i in index:
    if i == 0:
        if abs(a[i] - a[i + 2]) <= k or abs(a[i + 1] - a[i + 2]) <= k:
            cnt += 1
    elif i == n - 2:
        if abs(a[n - 2] - a[n - 3]) <= k or abs(a[n - 1] - a[n - 3]) <= k:
            cnt += 1
    else:
        if (abs(a[i] - a[i - 1]) <= k and abs(a[i] - a[i + 2]) <= k) or (abs(a[i + 1] - a[i - 1]) <= k and abs(a[i + 1] - a[i + 2]) <= k):
                cnt += 1
print(n - 2 * len(index) + cnt)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
x = []
y = []
z = []
tmp = int(input())
x.append(tmp)
y.append(tmp)
for i in range(n-1):
  t = int(input())
  if abs(t-tmp) <= k:
    x.append(t)
    tmp = t
  y.append(t)
tmp = y[1]
z.append(tmp)
for i in range(2,n):
  t = y[i]
  if abs(t-tmp) <= k:
    z.append(t)
    tmp = t
print(max(len(x),len(z)))