QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#286932 | #5592. Family Visits | mfshi03 | WA | 1226ms | 155152kb | Python3 | 1.4kb | 2023-12-19 08:36:38 | 2023-12-19 08:36:38 |
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[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)
Details
Tip: Click on the bar to expand more detailed information
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'