oj.uz

Submission #91614

# Submission time Handle Problem Language Result Execution time Memory
91614 2018-12-28T16:28:52 Z model_code Journey (NOI18_journey) Python 3
69 / 100
 2000 ms 17824 KB 
import sys
N, M, H = map(int, sys.stdin.readline().split())
adjList = [[] for i in range(N)]
dp = [[0]*M for i in range(N)]
for a in range(N-1):
	line = list(map(int, sys.stdin.readline().split()))
	for k in range(H):
		b = line[k*2]
		c = line[k*2+1]
		if b > a:
			adjList[b].append((a, c))

dp[0][0] = 1
for i in range(1, N):
	s = dp[i-1][0]
	for k in range(1, M):
		s += dp[i-1][k]
		dp[i-1][k] = s
	for k in range(M):
		q = 0
		for x, c in adjList[i]:
			if c <= k:
				q += dp[x][k-c]
				if q > 500000001:
					q = 500000001
					break
		dp[i][k] = q
		if q > 500000001 and i < N-1:
			break


print (" ".join(map(str, dp[N-1])))

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3400 KB Output is correct
2 Correct 21 ms 3340 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3368 KB Output is correct
2 Correct 22 ms 3340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3400 KB Output is correct
2 Correct 21 ms 3340 KB Output is correct
3 Correct 22 ms 3368 KB Output is correct
4 Correct 22 ms 3340 KB Output is correct
5 Correct 61 ms 3852 KB Output is correct
6 Correct 68 ms 3764 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3400 KB Output is correct
2 Correct 21 ms 3340 KB Output is correct
3 Correct 22 ms 3368 KB Output is correct
4 Correct 22 ms 3340 KB Output is correct
5 Correct 61 ms 3852 KB Output is correct
6 Correct 68 ms 3764 KB Output is correct
7 Correct 1587 ms 17824 KB Output is correct
8 Execution timed out 2053 ms 17548 KB Time limit exceeded
9 Halted 0 ms 0 KB -