QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#286932#5592. Family Visitsmfshi03WA 1226ms155152kbPython31.4kb2023-12-19 08:36:382023-12-19 08:36:38

Judging History

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

  • [2023-12-19 08:36:38]
  • 评测
  • 测评结果:WA
  • 用时:1226ms
  • 内存:155152kb
  • [2023-12-19 08:36:38]
  • 提交

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[0]
                else:
                    dp[(i, k)] = day[1] - 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


    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: 8128kb

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: 4ms
memory: 8156kb

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: 9ms
memory: 8184kb

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: 10ms
memory: 8156kb

input:

3 1
10 10
10 10
10 0
2

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 8256kb

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: 8ms
memory: 8168kb

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: 5ms
memory: 8164kb

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: 10ms
memory: 8176kb

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: 0
Accepted
time: 10ms
memory: 8176kb

input:

6 1
0 0
0 1
0 2
0 0
0 1
0 2
6

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 1226ms
memory: 155152kb

input:

999 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53...

output:

956

result:

ok single line: '956'

Test #11:

score: 0
Accepted
time: 646ms
memory: 95636kb

input:

997 1
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0
31 0
32 0
33 0
34 0
35 0
36 0
37 0
38 0
39 0
40 0
41 0
42 0
43 0
44 0
45 0
46 0
47 0
48 0
49 0
50 0
51 0
52 0
53 0
54 0
55 0
56 0
57 0
58 0
59 0
60 0
61 ...

output:

567

result:

ok single line: '567'

Test #12:

score: 0
Accepted
time: 400ms
memory: 79324kb

input:

758 1
499 0
500 0
501 0
502 0
503 0
504 0
505 0
506 0
507 0
508 0
509 0
510 0
511 0
512 0
513 0
514 0
515 0
516 0
517 0
518 0
519 0
520 0
521 0
522 0
523 0
524 0
525 0
526 0
527 0
528 0
529 0
530 0
531 0
532 0
533 0
534 0
535 0
536 0
537 0
538 0
539 0
540 0
541 0
542 0
543 0
544 0
545 0
546 0
547 0
...

output:

499

result:

ok single line: '499'

Test #13:

score: 0
Accepted
time: 147ms
memory: 30076kb

input:

500 1
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 ...

output:

340

result:

ok single line: '340'

Test #14:

score: 0
Accepted
time: 336ms
memory: 57788kb

input:

1000 1
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2...

output:

340

result:

ok single line: '340'

Test #15:

score: 0
Accepted
time: 661ms
memory: 95508kb

input:

997 1
322 0
216 0
418 0
179 0
519 0
391 0
556 0
23 0
400 0
505 0
190 0
577 0
162 0
502 0
223 0
54 0
181 0
560 0
333 0
508 0
409 0
455 0
353 0
255 0
413 0
458 0
463 0
143 0
373 0
158 0
551 0
221 0
399 0
174 0
284 0
147 0
406 0
71 0
401 0
208 0
236 0
184 0
149 0
491 0
39 0
507 0
228 0
72 0
21 0
282 0
...

output:

567

result:

ok single line: '567'

Test #16:

score: 0
Accepted
time: 350ms
memory: 57688kb

input:

1000 1
6 0
3 0
7 0
1 0
2 0
8 0
5 0
9 0
7 0
8 0
10 0
6 0
9 0
5 0
7 0
3 0
7 0
4 0
1 0
7 0
5 0
7 0
5 0
7 0
10 0
3 0
1 0
6 0
10 0
4 0
8 0
7 0
10 0
5 0
2 0
10 0
10 0
2 0
2 0
10 0
1 0
4 0
9 0
8 0
3 0
9 0
3 0
6 0
9 0
8 0
6 0
9 0
1 0
4 0
9 0
9 0
7 0
6 0
7 0
8 0
9 0
9 0
4 0
2 0
7 0
10 0
3 0
4 0
3 0
1 0
5 0
5...

output:

340

result:

ok single line: '340'

Test #17:

score: 0
Accepted
time: 7ms
memory: 8404kb

input:

1000 1000
207 363
789 986
722 813
73 821
461 790
403 761
489 746
42 285
415 536
565 669
983 994
561 978
610 961
371 851
857 997
365 559
935 988
258 731
296 827
850 854
437 646
184 206
599 802
725 976
207 495
568 664
118 669
376 493
377 429
232 284
810 995
255 404
43 709
562 894
239 477
970 982
184 8...

output:

997

result:

ok single line: '997'

Test #18:

score: 0
Accepted
time: 13ms
memory: 8452kb

input:

1000 500
309 243
53 202
232 7
411 924
307 250
433 815
496 487
311 470
52 229
325 943
3 32
244 319
226 56
273 895
318 344
415 558
377 82
477 811
476 92
379 910
109 356
496 702
260 488
46 179
283 331
472 523
322 465
80 182
497 157
164 681
279 206
422 748
292 16
139 426
422 498
178 453
34 373
94 463
37...

output:

692

result:

ok single line: '692'

Test #19:

score: -100
Wrong Answer
time: 8ms
memory: 8504kb

input:

1000 50
22 82
70 148
40 141
89 147
24 137
80 131
75 150
25 84
42 75
99 142
94 75
80 145
96 132
49 146
9 75
25 149
5 145
23 99
85 103
62 114
31 138
33 91
81 82
6 107
35 111
44 128
40 106
10 133
42 91
60 100
38 108
80 97
58 90
24 119
25 111
4 121
56 144
22 109
26 97
18 116
57 89
3 129
88 89
23 131
65 ...

output:

377

result:

wrong answer 1st lines differ - expected: '388', found: '377'