Problem:


Score : 200 points

Problem Statement

In a factory, there are N robots placed on a number line.
Robot i is placed at coordinate X_i and can extend its arms of length L_i in both directions, positive and negative.

We want to remove zero or more robots so that the movable ranges of arms of no two remaining robots intersect.
Here, for each i (1 \leq i \leq N), the movable range of arms of Robot i is the part of the number line between the coordinates X_i - L_i and X_i + L_i, excluding the endpoints.

Find the maximum number of robots that we can keep.

Constraints

1 \leq N \leq 100,000

0 \leq X_i \leq 10^9 (1 \leq i \leq N)

1 \leq L_i \leq 10^9 (1 \leq i \leq N)

If i \neq j, X_i \neq X_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 L_1
X_2 L_2
\vdots
X_N L_N

Output

Print the maximum number of robots that we can keep.

Sample Input 1

4
2 4
4 3
9 3
100 5

Sample Output 1

3

By removing Robot 2, we can keep the other three robots.

Sample Input 2

2
8 20
1 10

Sample Output 2

1

Sample Input 3

5
10 1
2 1
4 1
6 1
8 1

Sample Output 3

5



Sample input:
4
2 4
4 3
9 3
100 5


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
input = raw_input
#import numpy as np
def argmax(jamas_count):
    max_jama = max(jamas_count)
    max_i = jamas_count.index(max_jama)
    return max_i

n = int(input())

jamas = [[] for _ in range(n)]
jamas_count = [0 for _ in range(n)]

xs = []
ls = []
for i in range(n):
    x, l = map(int, input().split(" "))
    xs.append(x)
    ls.append(l)

    for j in range(0, i):
        if xs[j] < x:
            x1 = xs[j]
            l1 = ls[j]
            x2 = x
            l2 = l
        else:
            x1 = x
            l1 = l
            x2 = xs[j]
            l2 = ls[j]
        if x1 + l1 - 1 < x2 - l2 + 1:
            pass
        else:
            jamas[i].append(j)
            jamas[j].append(i)
            jamas_count[i] += 1
            jamas_count[j] += 1



def find_max_jama():
    max_i = argmax(jamas_count)
    return max_i

n_remove = 0

out = 0
ones = []
others = []
for j in range(n):
    if jamas_count[j] == 0:
        out += 1
        continue
    if jamas_count[j] == 1:
        ones.append(j)
    else:
        others.append(j)

len_aites = len(ones)
while len_aites >= 1:
    jibun = ones[0]
    aite = jamas[jibun][0]
    ones = ones[1:]
    out += 1
    len_aites -= 1

    aite_aites = jamas[aite]
    aite_aites.remove(jibun)
    if len(aite_aites) == 0:
        ones.remove(aite)
        len_aites -= 1
        

    for aite_aite in aite_aites:
        jamas[aite_aite].remove(aite)
        jamas_count[aite_aite] -= 1
        if jamas_count[aite_aite] == 1:
            ones.append(aite_aite)
            len_aites += 1
        elif jamas_count[aite_aite] == 0:
            out += 1
            ones.remove(aite_aite)
            len_aites -= 1

print(out)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
d = dict()
incl = dict()
for i in range(N):
  tmp = input().split(" ")
  d[int(tmp[0])] = int(tmp[1])
  incl[int(tmp[0])] = 0
  rm=0
  f = 0
while f==0 or sum(incl.values()) >0:
  for i in d:
    if i in incl:
      incl[i] = 0
  f=1
  for i in d:#このロボットが
    for j in d:#このロボットを含んでいるか
      if i!=j and i-d[i] <j< i+d[i]:
        if i in incl:
          incl[i] += 1
  m = max(incl.values())
  for i in d:
    if (i in incl) and incl[i]==m and m>0:
      del incl[i],d[i]
      rm+=1
      break
print(N-rm)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
import math
import numpy as np

lob_list = []
for i in range(n):
	array = list(map(int, input().split()))
	lob_list.append(array)
	
arm_list = []
for i in range(n):
	a = range(lob_list[i][0]-lob_list[i][1]+1, lob_list[i][0]+lob_list[i][1])
	arm_list.append(a)
	
v = []
flag = True
while flag:	
	for i in range(n):
		v = arm_list[i]
		if i != n-1:
			for ii in range(lob_list[i][1]*2 - 1) :
				for iii in range(n):
					if v[ii] in arm_list[iii] and i != iii :
						if lob_list[i][1] > lob_list[iii][1] :
							n -= 1
							new = np.delete(lob_list, i, 0)
							continue
						else:
							n -= 1
							new = np.delete(lob_list, iii, 0)
							continue
					else:
						pass
		else :
			for ii in range(lob_list[i][1]*2 - 1) :
				for iii in range(n):
					if v[ii] in arm_list[iii] and i != iii :
						if lob_list[i][1] > lob_list[iii][1] :
							n -= 1
							new = np.delete(lob_list, i, 0)
							continue
						else:
							n -= 1
							new = np.delete(lob_list, iii, 0)
							continue
					else:
						pass		
			flag = False

print(n)

Submission status: Time Limit Exceeded

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

sen_list = []
for robot in robots:
  sen_list.append([robot[0]-robot[1],robot[0]+robot[1]])

sen_result = []
for sen in sen_list:
  sen_result.append(str(len([s for s in sen_list if (s[0] < sen[0] and sen[0] < s[1]) or (s[0] < sen[1] and sen[1] < s[1]) or (sen[0] < s[0] and s[1] < sen[1])])))

calc_text = ''.join(sen_result)


res_text = calc_text.replace("11","1")

res_list = [x for x in list(map(int, list(res_text))) if x < 2]

res = len(res_list)
print(res)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    readline = sys.stdin.readline
    N = int(readline())
    info = [None] * N
    for i in range(N):
        p, l = map(int, input().split())
        info[i] = [p-l, p+l]
    info.sort(key=lambda x: x[0])

    def is_obstacle(i):
        count = 0
        for j in info[i+1:]:
            if info[i][1] > j[0]:
                count += 1
        for j in info[:i]:
            if info[i][0] < j[1]:
                count += 1
        return count

    obs_list = [1] * N
    while sum(obs_list) > 0:
        obs_list = [0] * N
        m = 0
        idx = 0
        for i in range(N):
            obs_list[i] = is_obstacle(i)
            if m < obs_list[i]:
                m = obs_list[i]
                idx = i
        if sum(obs_list) == 0:
            break
        info = info[:idx] + info[idx+1:]
        N -= 1

    print(N)

resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = [list(map(int,input().split())) for i in range(N)]
s.sort()
for index, arm in enumerate(s):
  if index+1 == len(s):
    break
  if index >0:
    if arm[0]+arm[1]>s[index+1][0]-s[index+1][1] and arm[0]-arm[1] < s[index-1][0]+s[index-1][1]:
      s.remove(arm)

for index, arm in enumerate(s):
  if index+1 == len(s):
    break
  if arm[0]+arm[1] > s[index+1][0]-s[index+1][1]:
    s.pop(index+1)
  
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
Row=int(input())
List=[list(map(int,input().split())) for i in range(Row)]

mylist={}
for i in range(Row):
	mylist[i]=[List[i][0]-List[i][1],List[i][0]+List[i][1]]

ct_result=0
l=list()
for x in range(Row):
  ct={}
  for j in range(Row):
      ct[j]=0
      for k in range(Row):
        if j not in l and k not in l:
          if j!=k:
              if  (mylist[j][0] < mylist[k][0] and mylist[j][1] > mylist[k][0]) or (mylist[j][0] < mylist[k][1] and mylist[j][1] > mylist[k][1]):
                  ct[j]+=1
  if max(ct.values()) == 0:
      result =Row-ct_result
      break
  else:
    mylist.pop(max(ct, key=ct.get))
    l.append(max(ct, key=ct.get))
    ct_result+=1
	
          
print(result)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X_list = []
L_list = []
for i in range(N):
    X, L = map(int, input().split())
    X_list.append(X)
    L_list.append(L)
    
mixed = zip(X_list, L_list)
mixed_sort = sorted(mixed)
 
for i in range(len(mixed_sort)):
    val = mixed_sort[i]
    X_list[i] = val[0] 
    L_list[i] = val[1]
       
rem_count = -1
dob_count = 1 
while dob_count != 0:
    rem_count += 1
    dob_count = 0
    X_min = []
    X_max = []
    X_count = []
    for i in range(len(X_list)):
        X_min.append(X_list[i]-L_list[i])
        X_max.append(X_list[i]+L_list[i])
        
    for i in range(len(X_list)):
        if i == 0:
            val = len(X_list)-1
            for j in range(1,len(X_list)):
                if X_max[0] <= X_min[j]:
                    val = j-1
                    break
            X_count.append(val)
            if val != 0:
                dob_count += 1
            
        elif i == len(X_list)-1:
            val = len(X_list)-1
            for j in range(len(X_list)-1):
                if X_max[len(X_list)-1] < X_min[j]:
                    val = j
                    break
            val = len(X_list)-1-val
            X_count.append(val)
            if val != 0:
                dob_count += 1
            
        else:
            val_1 = len(X_list)-i-1
            for j in range(i+1,len(X_list)):
                if X_max[i] <= X_min[j]:
                    val_1 = j-i-1
                    break
            
            val_2 = i
            for j in range(i):
                if X_min[i] >= X_max[j]:
                    val_2 = j
                    break
            
            val = val_1 + val_2
            X_count.append(val)
            if val != 0:
                dob_count += 1
        
    val_max = max(X_count)
    if not val_max == 0:
        val_index = X_count.index(val_max)
        del(X_list[val_index:val_index+1])
        del(L_list[val_index:val_index+1])
    
print(N-rem_count)

Submission status: Time Limit Exceeded

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


sorted(x_l)

x_l_max =[]
x_l_min =[]

for i in range(N):
    x_l_max.append(x_l[i][0] + x_l[i][1])
    x_l_min.append(x_l[i][0] - x_l[i][1])

obstacle_cnt_list =[]
obstacle_cnt = -1

for i in range(N):
    for j in range(len(x_l_min)):
        if x_l_min[j] <= int(x_l[i][0]) and int(x_l[i][0]) <= x_l_max[j]:
            obstacle_cnt = obstacle_cnt +1
        else:
            break
    obstacle_cnt_list.append(obstacle_cnt)
    obstacle_cnt = -1

# print(obstacle_cnt_list)

max_value = max(obstacle_cnt_list)

# print( N - max_value)

maxIndex = [i for i, x in enumerate(obstacle_cnt_list) if x == max(obstacle_cnt_list)]

# print(maxIndex)
# print(len(maxIndex))

if max_value ==0:
    print(N)
else:
    print(int(N - len(maxIndex)/2))

Submission status: Time Limit Exceeded

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

x_l_max =[]
x_l_min =[]

for i in range(N):
    x_l_max.append(int(x_l[i][0]) + int(x_l[i][1]))
    x_l_min.append(int(x_l[i][0]) - int(x_l[i][1]))
    
# print(x_l_min)
# print(x_l_max)
# print(int(x_l[2][0]) )
    
obstacle_cnt_list =[]
obstacle_cnt = -1

for i in range(N):
    for j in range(len(x_l_min)):
        if x_l_min[j] <= int(x_l[i][0]) and int(x_l[i][0]) <= x_l_max[j]:
            obstacle_cnt = obstacle_cnt +1
    obstacle_cnt_list.append(obstacle_cnt)
    obstacle_cnt = -1

# print(obstacle_cnt_list)

max_value = max(obstacle_cnt_list)

# print( N - max_value)

maxIndex = [i for i, x in enumerate(obstacle_cnt_list) if x == max(obstacle_cnt_list)]

# print(maxIndex)
# print(len(maxIndex))

if max_value ==0:
    print(N)
else:
    print(int(N - len(maxIndex)/2))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
l = []
for i in range(N):
  l.append(list(map(int, input().split())))
l.sort(key=lambda x : x[1])  
ans_l = []
ans = 0
  
for i in range(N):
  tmp = list(range(max(0, l[i][0]-l[i][1]+1), l[i][0]+l[i][1]))
  if len(ans_l) == len(list(set(ans_l)-set(tmp))):
    ans_l = tmp + ans_l
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
alllist = []
remain = 0
for i in range(N):
    X, L = map(int,input().split())
    alllist.append([i for i in range(X-L,X+L)])
d = 0
l = alllist
for i in range(N):
    kumiawase = N-i
    c_list = list(itertools.combinations(l, kumiawase))
    for j in range(len(c_list)):
        first = c_list[j][0]
        c= 1
        for k in range(len(c_list[j])-1):
            if len(set(c_list[j][k+1]) & set(first)) == 0:
                first += c_list[j][k+1]
                c += 1
            else:
                break
        if c == kumiawase:
            print(kumiawase)
            d = 1
            break
        else:
            pass
    if d == 1:
        break
    else:
        pass

Submission status: Time Limit Exceeded

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



for i in range(n):
    left.append((l[i][0]-l[i][1],l[i][0]+l[i][1]))
left.sort()   
count = 1
right = 10**10
for i in range(n):
    right = min(right,left[i][1])

while True:
    right2 = 10**10
    for i in range(n):
        if left[i][0] >= right:
            
            right2 = min(right2,left[i][1])
            
            
    if right2 == 10**10:
        print(count)
        exit()
    else:
        right = right2
        count += 1

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    readline = sys.stdin.readline
    N = int(readline())
    info = [None] * N
    for i in range(N):
        p, l = map(int, input().split())
        info[i] = [p-l, p+l]
    info.sort(key=lambda x: x[0])

    def is_obstacle(i):
        count = 0
        for j in info[i+1:]:
            if info[i][1] > j[0]:
                count += 1
        for j in info[:i]:
            if info[i][0] < j[1]:
                count += 1
        return count

    obs_list = [1] * N
    while sum(obs_list) > 0:
        obs_list = [0] * N
        m = 0
        idx = 0
        for i in range(N):
            obs_list[i] = is_obstacle(i)
            if m < obs_list[i]:
                m = obs_list[i]
                idx = i
        if sum(obs_list) == 0:
            break
        info = info[:idx] + info[idx+1:]
        N -= 1

    print(N)

resolve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
alllist = []
remain = 0
for i in range(N):
    X, L = map(int,input().split())
    alllist.append([X-L,X+L])
d = 0
l = alllist
for i in range(N):
    kumiawase = N-i
    c_list = list(itertools.combinations(l, kumiawase))
    for j in range(len(c_list)):
        first = [q for q in range(c_list[j][0][0],c_list[j][0][1])]
        c= 1
        for k in range(len(c_list[j])-1):
            if len(set([r for r in range(c_list[j][k+1][0],c_list[j][k+1][1])]) & set(first)) == 0:
                first += [r for r in range(c_list[j][k+1][0],c_list[j][k+1][1])]
                c += 1
            else:
                break
        if c == kumiawase:
            print(kumiawase)
            d = 1
            break
        else:
            pass
    if d == 1:
        break
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:
s=int(input())
t=[list(map(int, input().split())) for i in range(s)]
t.sort()
u=[]
u.append(0)
a=t[0][0]+t[0][1]
for j in range(1,s):
  c=t[j][0]-t[j][1]
  if a<=c:
    a=t[j][0]+t[j][1]      
  else:
    a=t[j][0]+t[j][1]
    u.append(j)
d=0
for l in u:
  e=0
  for i in range(l,s):
    if i==l:
      a=t[i][0]+t[i][1]
      e+=1
    else:
      c=t[i][0]-t[i][1]
      if a<=c:
        e+=1
        a=t[i][0]+t[i][1]
  d=max(d,e)
print(d)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
robots = [[int(i) for i in input().split()] for i in range(n)]

min_sub = 1000
flag = 0

for i in range(n):

    robot = robots[i]
    arm = (robot[0] - robot[1], robot[0] + robot[1])
    sub = 0
    for j in range(n):
        if i == j:
            continue
        else:
            robot = robots[j]
            n_arm =  (robot[0] - robot[1], robot[0] + robot[1])

            if (arm[1] > n_arm[0] and arm[0] < n_arm[0]) or arm[0] > n_arm[0] and arm[0] < n_arm[1]:
                sub += 1
                flag = 1
    if sub != 0:
        min_sub = min(min_sub, sub)
if flag == 0:
    print(n)
else:
    print(n - min_sub)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
l = []
for i in range(N):
  l.append(list(map(int, input().split())))
  l.sort(key=lambda x : x[1])  
ans_l = []
ans = 0
  
for i in range(N):
  tmp = list(range(max(0, l[i][0]-l[i][1]+1), l[i][0]+l[i][1]))
  if len(ans_l) == len(list(set(ans_l)-set(tmp))):
    ans_l = tmp + ans_l
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
pre = None
robots = list()
for i in range(N):
    a, b = map(int, input().split())
    robots.append({"X": a, "L":  a - b, "R": a + b})
robots.sort(key=lambda x: x['X'])
c = dict()
tc = 0
for x in robots:
    for y in robots:
        if x["X"] == y["X"]:
            continue
        if x["R"] <= y["L"] or x["L"] >= y["R"]:
            continue
        if x["X"] not in c:
            c[x["X"]] = {"c": 0, "t": set()}
        c[x["X"]]["c"] += 1
        tc += 1
        c[x["X"]]["t"].add(y["X"])
if len(c) == 0:
    print(N)
    exit()
cc = list({"X": x, "c": c[x]["c"]} for x in c)
cc.sort(key=lambda x: x["c"], reverse=True)

for x in cc:
    N -= 1
    tc -= len(c[x["X"]]["t"])
    for y in c[x["X"]]["t"]:
        c[y]["t"].remove(x["X"])
        tc -= 1
    del c[x["X"]]
    if tc == 0:
        print(N)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
alllist = []
remain = 0
for i in range(N):
    X, L = map(int,input().split())
    alllist.append([X-L,X+L])
d = 0
l = alllist
for i in range(N):
    kumiawase = N-i
    c_list = list(itertools.combinations(l, kumiawase))
    for j in range(len(c_list)):
        first = [q for q in range(c_list[j][0][0],c_list[j][0][1])]
        c= 1
        for k in range(len(c_list[j])-1):
            if len(set(r for r in range(c_list[j][k+1][0],c_list[j][k+1][1])) & set(first)) == 0:
                c += 1
            else:
                break
        if c == kumiawase:
            print(kumiawase)
            d = 1
            break
        else:
            pass
    if d == 1:
        break
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
list = [list(map(int, input().split())) for i in range(n)]
ans = []
list.sort(key=lambda x: x[0])

for i in range(n-1):
    a = list[i][0] + list[i][1]
    b = list[i+1][0] - list[i+1][1]
    if a > b:
        if not(list[i][0] in ans):
            ans.append(list[i+1][0])
        elif list[i-1][0] + list[i-1][1] > b:
            ans.append(list[i+1][0])
        i += 2
print(n - len(ans))

Submission status: Time Limit Exceeded

Solution code:
import time
N = int(input())
X = []; L = []
for _ in range(N):
    X_tmp, L_tmp = [int(x) for x in input().split()]
    X.append(X_tmp)
    L.append(L_tmp)

dup = {}
for i in range(N - 1):
    for j in range(i + 1, N):
        if X[i] - L[i] < X[j] + L[j] and X[i] + L[i] > X[j] - L[j]:
            if i in dup:
                dup[i].append(j)
            else:
                dup[i] = [j]
            if j in dup:
                dup[j].append(i)
            else:
                dup[j] = [i]

size_max = 0
for i in dup:
    if len(dup[i]) > size_max:
        size_max = len(dup[i])

size = {}
for i in range(size_max):
    size[i + 1] = []

for i in dup:
    size[len(dup[i])].append(i)

ans = 0
while len(dup) > 0:
    t = size[max(size.keys())][0]
    for s in dup[t]:
        if len(dup[s]) == 1:
            size[1].remove(s)
            del dup[s]
        else:
            size[len(dup[s])].remove(s)
            size[len(dup[s]) - 1].append(s)
            dup[s].remove(t)
    size[len(dup[t])].remove(t)
    del dup[t]
    ans += 1
ans = N - ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [input().split() for _ in range(N)]
 
ans = []
before_count = 0
 
 
def has_duplicates(seq):
    return len(seq) != len(set(seq))
 
 
def open(list):
    retval = [int(list[0])]
    for i in range(1, int(list[1])):
        retval.append(int(list[0]) + i)
        retval.append(int(list[0]) - i)
    return retval
 
 
# list = open(A_list[0]) + open(A_list[1])
#
# print(list)
 
for i in range(2 ** len(A_list)):
    ans = []
    count = 0
    for j in range(len(A_list)):
        if (i >> j) & 1:
            count += 1  # 使用している個数
            ans += open(A_list[len(A_list) - 1 - j])
 
    if not has_duplicates(ans):
        if count > before_count:
            before_count = count
 
print(before_count)

Submission status: Time Limit Exceeded

Solution code:
max_num = 1000000000

N = int(input())

robots = []
conflict_counts = []
for _ in range(N):
  x, l = map(int, input().split())
  robot = {}
  start = x - l + 1
  start = start if 0 < start else 0 
  end = x + l -1
  end = end if end < max_num else max_num
  robot['start'] = start
  robot['end'] = end
  robot['conflict_ids'] = []
  robot['removed'] = False
  robots.append(robot)
  conflict_counts.append(0)

robots = sorted(robots, key=lambda x:x['end'])
robots = sorted(robots, key=lambda x:x['start'])

for i in range(N-1):
  ckeck_target = robots[i]
  end = ckeck_target['end']

  for j in range(i+1, N):
    if j in ckeck_target['conflict_ids']:
      continue
    compare = robots[j]
    if compare['start'] <= end:
      for s in range(i, j)[::-1]:
        robots[s]['conflict_ids'].append(j)
        conflict_counts[s] += 1
        compare['conflict_ids'].append(s)
        conflict_counts[j] += 1
    else:
      break

while 0 < max(conflict_counts):
  remove_robot_id = conflict_counts.index(max(conflict_counts))
  remove_robot = robots[remove_robot_id]
  remove_robot['removed'] = True
  conflict_counts[remove_robot_id] = 0
  for i in remove_robot['conflict_ids']:
    robots[i]['conflict_ids'].remove(remove_robot_id)
    conflict_counts[i] -= 1

print(len(list(filter(lambda robot: not robot['removed'], robots))))

Submission status: Time Limit Exceeded

Solution code:
X = []
L = []
N = int(input())
for i in range(N):
    a,b = input().split()
    a = int(a)
    b = int(b)
    X.append(a)
    L.append(b)
X_range = []
for i in range(N):
    a = []
    a.append(X[i] - L[i])
    a.append(X[i]+L[i])
    X_range.append(a)
t_count = [[0 for i in range(N)] for i in range(N)]
for i in range(N):
    for t in range(N):
        if X_range[i][0]< X_range[t][0]  < X_range[i][1] or X_range[i][0]< X_range[t][1]  < X_range[i][1]:
            t_count[t][i] = 1


while True :

    t_sum = [0 for i in range(len(t_count))]
    for i in range(len(t_count)):
        t_sum[i] = sum(t_count[i])

    if sum(t_sum)==0:
        print(len(t_count))
        break
    index = t_sum.index(max(t_sum))

    for i in range(len(t_count)):
        t_count[i][index]=0
 
    del t_count[index]

Submission status: Time Limit Exceeded

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

d = list(range(0))
for i in range(n):
    b = a[i][0] - a[i][1]
    c = a[i][0] + a[i][1]
    d.append([b,c])

def aaa():
  #print(d)
  e = list(range(0))
  mcnt = 0
  f = 0 
  for i in range(len(d)):
    cnt = 0
    #print(i)
    for j in range(len(d)):
      
      if i != j :      
        if (d[i][0] < d[j][0] and d[i][1] > d[j][0]) or (d[i][0] < d[j][1] and d[i][1] > d[j][1]):
          cnt = cnt + 1
          #print(cnt)
    if cnt > 0 and mcnt < cnt:
      mcnt = cnt
      f = i  
  #print(mcnt)
  if mcnt > 0 :
    d.pop(f)
    #print('pop')
  return mcnt
    
x = 1
while x > 0 :
  x = aaa()
  #print(x)


    
print(len(d))

Submission status: Time Limit Exceeded

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

robots.sort(key=lambda hw: hw[0])


removed = 0
collision= {i: [] for i in range(n)}
for i, (hi, wi) in enumerate(robots):
  right = hi + wi
  for k, (hj, wj) in enumerate(robots[i+1:]):
    if hj - wj < right:
      if len(collision[i]) > 0:
        for c in collision[i]:
          collision[c].remove(i)
        removed += 1
        del collision[i]
        break;
      collision[i].append(i + k + 1)
      collision[i + k + 1].append(i)  
    else:
      break

for i in range(n):
  if collision.get(i) == []:
    del collision[i]

print(n - removed - len(collision) // 2)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
l.sort()
for i in range(0,n-1):
    if l[i+1][0]-l[i][0]<l[i+1][1]+l[i][1]:
        del l[i+1]
        l=[[0,0]]+l
        n-=1
print(n)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


dat = []
for _ in range(n):
    x, l = map(int, input().split())
    #           0  1   2    3    4co     5
    dat.append([x, l, x-l, x+l, 0     , []])
dat.sort(key = lambda x: x[1], reverse=True)
#print(dat)
res = []
res_safe = []
def do_count():
    for i in range(n):
        #print("i={0}".format(i))
        c = 0
        m = []
        for j in range(i+1, n):
            #print("j={0}".format(j))
            if dat[j][3] <= dat[i][2] or dat[i][3] <= dat[j][2]:
                pass
            else:
                dat[i][5].append(dat[j])
                dat[j][5].append(dat[i])
                dat[i][4] += 1
                dat[j][4] += 1

do_count()
dat.sort(key = lambda x: (x[4], x[1]), reverse=True)
#print(dat)
for i in range(n):
    if dat[i][4] == 0:
        res.append(dat[i])
        continue
    #print("node {0}: kill".format(i))
    for node in dat[i][5]:
        #print(node[5])
        for x in range(len(node[5])):
            if node[5][x] == dat[i]:
                node[4] -= 1
                del node[5][x]
                #print("!!!!")

#print(res)
print(len(res))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
input = sys.stdin.readline
XL = []
for _ in range(N):
    x, l = map(int, input().split())
    XL.append((x, l))
XL.sort()
#print(XL)

ANS = [(0, -1*10**9-1), (1, XL[0][0]+XL[0][1])]
import bisect
for x, l in XL[1:]:
    new_right = x+l
    new_left = x-l
    
    new_num = 0
    for num, right in reversed(ANS):
        if right > new_left:
            continue
        else:
            new_num = max(new_num, num+1)
            break
    bisect.insort(ANS, (new_num, new_right))
    
#ans_num = 0
#for num, _ in ANS:
#    ans_num = max(ans_num, num)
#print(ans_num)
print(ANS[-1][0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

X_L_list = []

for i in range(N):
    x1,l1=[int(i) for i in input().split()]
    X_L_list.append([x1,l1])

X_L_list.sort()

batting_count_list = []
batting_target_list = []

for i in range(len(X_L_list)):
  batting_count_list.append(0)
  batting_target_list.append([])

for i in range(len(X_L_list)):
  batting_count = 0
  batting_target = []
  for j in range(i+1,len(X_L_list)):
    if(abs(X_L_list[i][0]-X_L_list[j][0]) < X_L_list[i][1]+X_L_list[j][1]):
      batting_count_list[i] += 1
      batting_count_list[j] += 1
      batting_target_list[i].append(j)
      batting_target_list[j].append(i)

while True:
  max_batting_count = max(batting_count_list)
  if(max_batting_count != 0):
    max_index = batting_count_list.index(max_batting_count)
    for i in batting_target_list[max_index]:
      batting_count_list[i] -= 1
      batting_target_list[i].remove(max_index)
    X_L_list.pop(max_index)
    batting_count_list.pop(max_index)
    batting_target_list.pop(max_index)
  else:
    break

print(len(X_L_list))

Submission status: Time Limit Exceeded

Solution code:
def delete_max_line(arr):
    max_i=0
    M=0
    i=0

    for a in arr:
        s=sum(a)
        if M<s:
            M=s
            max_i=i
        i+=1

    arr.pop(max_i)
    for a in arr:
        a.pop(max_i)

    return M

N=int(input())
XL=[]

for i in range(N):
    x,l=input().split(" ")
    XL.append([int(x),int(l)])

XL.sort()

attach=[[0]*N for i in range(N) ]

right=[xl[0]+xl[1] for xl in XL]
left=[xl[0]-xl[1] for xl in XL]

for i in range(N-1):
    for j in range(i+1,N):
        if right[i]>left[j]:
            attach[i][j]=1
            attach[j][i]=1



ans=0
while True:
    judge=delete_max_line(attach)
    if judge==0:
        break
    ans+=1

print(N-ans)

Submission status: Time Limit Exceeded

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

n = int(input())
list = [list(map(int, input().split())) for i in range(n)]
ans = []
list.sort(key=lambda x: x[0])

for i in range(n-1):
    if list[i][0] + list[i][1] > list[i+1][0] - list[i+1][1]:
        if not(list[i][0] in ans):
            ans.append(list[i+1][0])
        elif list[i-1][0] + list[i-1][1] > list[i+1][0] - list[i+1][1]:
            ans.append(list[i+1][0])
        i += 2
print(n - len(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
grid = []
armbuffer = 0
checkflag = 0

for i in range(N):
    array = list(map(int, input().strip().split()))
    grid.append(array)

grid.sort()

for j in range(len(grid), 0, -1):
    if j == 1:
        print(1)
        break
    for k in itertools.combinations(grid, j):
        k = list(k)
        for l in range(j - 1):
            if k[l+1][0]-k[l][0]<k[l+1][1]+k[l][1]:
                break
        else:
            print(j)
            break
    else:
        continue
    break

Submission status: Time Limit Exceeded

Solution code:
Row=int(input())
List=[list(map(int,input().split())) for i in range(Row)]

mylist={}
for i in range(Row):
	mylist[i]=[List[i][0]-List[i][1],List[i][0]+List[i][1]]

ct_result=0
l=list()
for x in range(Row):
  ct={}
  for j in range(Row):
      ct[j]=0
      for k in range(Row):
        if j not in l and k not in l:
          if j!=k:
              if  (mylist[j][0] < mylist[k][0] and mylist[j][1] > mylist[k][0]) or (mylist[j][0] < mylist[k][1] and mylist[j][1] > mylist[k][1]):
                  ct[j]+=1
  if max(ct.values()) == 0:
      result =Row-ct_result
      break
  else:
    mylist.pop(max(ct, key=ct.get))
    l.append(max(ct, key=ct.get))
    ct_result+=1
	
          
print(result)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x,l,dcnt=[0]*n,[0]*n,[0]*n
xlr=[[0]*2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  x[i],l[i]=a,b
  xlr[i]=[a-b,a+b]
xlr.sort()
for i in range(n-1):
  chk=xlr[i][1]
  cnt=0
  for j in range(i+1,n):
    if xlr[j][0]<chk:
      cnt+=1
    else:
      break
  dcnt[i]=cnt
cnt=0
for i in range(1,n+1):
  if dcnt[n-i]>0:
    dcnt[n-i]=0
    cnt+=1
    for j in range(n-i):
      if dcnt[n-i-j-1]>j:
        dcnt[n-i-j-1]-=1
print(n-cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
data = []
for _ in range(N):
	x, l = map(int, input().split())
	data.append((x, l))

data.sort()

states = { -10 ** 9 - 1: 0 }

for x, l in data:
	new_states = {}
	for r, c in states.items():
		new_states[r] = c
		if r < x - l + 1:
			p = x + l - 1
			if p not in new_states or new_states[p] < c + 1:
				new_states[x + l - 1] = c + 1
	states = new_states

print(max((c for r, c in states.items())))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
x={}
y={}
for i in range(N):
    x[i],y[i] = map(int, input().split())

Red = N

loop=0
for i in range(N):
    loop += 1
    for j in range(loop,N):
            ABS=abs(x[i]-x[j])
#            print(ABS)
            if ((ABS<y[i]) or (ABS<y[j])):
                Red -= 1

print(Red)