QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#286931 | #5592. Family Visits | mfshi03 | WA | 10ms | 8260kb | Python3 | 1.5kb | 2023-12-19 08:30:56 | 2023-12-19 08:30:56 |
Judging History
answer
# Attempt 2
n, d = map(int, input().split())
days = [list(map(int, input().split())) for i in range(n)]
visits = [int(input()) for i in range(d)]
prefix = [0 for i in range(n + 1)]
for i in range(n):
prefix[i+1] = days[i][0] + prefix[i]
dp = dict()
sol = 0
def solve(start, n):
#print("start", start, n)
s = n - start + 1
for k in range(s+1):
for i, day in reversed(list(enumerate(days[start:n+1], 1))):
if i == s:
if k == 0:
dp[(i, k)] = day[1] - day[0]
else:
dp[(i, k)] = -day[0]
#if dp[(i,k)] < 0:
# return float("-inf")
else:
allowed = min(day[1], prefix[start + i] - prefix[start])
#print("allowed", start + i - 1, start, prefix[start + i] - prefix[start])
if k > 0:
dp[(i, k)] = max(dp[(i + 1, k)] - day[0], dp[(i + 1, k - 1)] + allowed - day[0])
else:
dp[(i, k)] = dp[(i + 1, k)] - day[0]
#print(i, k, dp[(i, k)])
if dp[(1, k)] >= 0:
return k + 1
return float("-inf")
start = 0
np = False
for v in visits:
add = solve(start, v - 1)
start = v
dp = dict()
if add < 0:
np = True
break
sol += add
if np:
print(-1)
else:
print(sol)
詳細信息
Test #1:
score: 100
Accepted
time: 10ms
memory: 8168kb
input:
6 2 1 2 2 1 1 4 3 2 3 6 2 3 3 6
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 8ms
memory: 8084kb
input:
10 5 12 10 0 2 7 1 1 8 3 4 3 4 2 3 1 2 10 1 7 5 2 4 5 6 8
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 10ms
memory: 8176kb
input:
10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 9ms
memory: 8260kb
input:
3 1 10 10 10 10 10 0 2
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 9ms
memory: 8220kb
input:
12 1 1 1 1 1 1 1 0 4 1 1 1 1 1 1 0 6 1 1 1 1 1 1 0 4 12
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 10ms
memory: 8156kb
input:
6 1 1 0 1 0 1 2 1 0 1 0 1 2 6
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 10ms
memory: 8232kb
input:
9 1 1 0 1 0 1 9 1 0 1 0 1 2 1 0 1 0 1 3 9
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 9ms
memory: 8156kb
input:
6 1 1 0 1 0 1 2 1 0 1 0 1 4 6
output:
2
result:
ok single line: '2'
Test #9:
score: -100
Wrong Answer
time: 10ms
memory: 8256kb
input:
6 1 0 0 0 1 0 2 0 0 0 1 0 2 6
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'