Submission #1188025

#TimeUsernameProblemLanguageResultExecution timeMemory
1188025esomerBouquet (EGOI24_bouquet)Pypy 3
70 / 100
3095 ms63588 KiB
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...