def solve():
n = int(input())
segments = []
mxLR = 0
for _ in range(n):
l, r = map(int, input().split(" "))
segments.append((l, r))
mxLR = max(mxLR, max(l, r))
if n <= 1000:
dp = [0] * n
for i in range(n):
l, r = segments[i]
dp[i] = 1
for j in range(i-l-1, -1, -1):
if j < 0: break
l2, r2 = segments[j]
if j + r2 < i:
dp[i] = max(dp[i], dp[j] + 1)
# print(dp)
print(max(dp))
elif mxLR <= 2:
dp = [0] * n
for i in range(n):
l, r = segments[i]
dp[i] = 1
for j in range(max(i-10, 0), i-l):
if j < 0: continue
l2, r2 = segments[j]
if j + r2 < i and j < i-l:
dp[i] = max(dp[i], dp[j] + 1)
# print(dp)
print(max(dp))
else:
dp = [0] * n
for i in range(n):
l, r = segments[i]
dp[i] = max(dp[i-1], 1)
for j in range(i-l-1, -1, -1):
if j < 0: continue
l2, r2 = segments[j]
if j + r2 < i:
dp[i] = max(dp[i], dp[j] + 1)
break
print(max(dp))
# let dp[i] be the maximum amount of tulips we can pick up in the i-th point, if we have boundaries l, r. then we can see that dp[i] = max(dp[i-1], dp[j] + 1)
# for some j < i such that i-j >= l and i-j >= r_j
# so now we just need to find the first tulip j in point 0, i-l such that
solve()
Compilation message (stdout)
Compiling 'Main.py'...
=======
adding: __main__.pyc (deflated 45%)
=======
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |