QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#286931#5592. Family Visitsmfshi03WA 10ms8260kbPython31.5kb2023-12-19 08:30:562023-12-19 08:30:56

Judging History

你现在查看的是最新测评结果

  • [2023-12-19 08:30:56]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:8260kb
  • [2023-12-19 08:30:56]
  • 提交

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'