Submission #1328026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1328026		username77	Trains (BOI24_trains)	Pypy 3	0 / 100	1971 ms	53636 KiB

Main

# BOI 2024 - Trains problem solution

MOD = 17  # Output modulo 10 + 7

# Read input
N = int(input())
trains = [None]  # 1-indexed array, so put a dummy at index 0
for _ in range(N):
    d, x = map(int, input().split())
    trains.append((d, x))

# Initialize DP array
dp = [0] * (N + 2)  # dp[i] = number of journeys starting at city i

# Compute DP from last city down to first
for i in range(N, 0, -1):
    dp[i] = 1  # journey that stays at city i
    d, x = trains[i]
    if d == 0:
        continue  # no train from this city
    for t in range(1, x + 1):
        j = i + t * d
        if j > N:
            break
        dp[i] = (dp[i] + dp[j]) % MOD

# Output answer: number of journeys starting at city 1
print(dp[1])

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 23%)

=======

• Subtask 1: 0 / 8
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29