Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- data = open('26.txt').readlines()
- n, k, Q = map(int, data[0].split())
- a = []
- for e in data[1:]:
- a.append(tuple(map(int, e.split())))
- a.sort()
- inf = 10000000
- mx_s = a[-1][0]
- dp = [[inf for j in range(Q + 1)] for i in range(mx_s + 1)]
- cur_a = -1
- mn = inf
- for i in range(1, mx_s + 1):
- if cur_a != n - 1 and a[cur_a + 1][0] == i:
- cur_a += 1
- if cur_a != -1:
- mn = min(mn, a[cur_a][1])
- dp[i][1] = mn
- for q in range(2, Q + 1):
- cur_a = -1
- mn = inf
- for i in range(1, mx_s + 1):
- if cur_a != n - 1 and a[cur_a + 1][0] == i:
- cur_a += 1
- if a[cur_a][0] == i and i - k >= 1:
- mn = min(dp[i - k][q - 1] + a[cur_a][1], mn)
- dp[i][q] = mn
- else:
- dp[i][q] = mn
- print(dp[mx_s][Q])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
