QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #523974 | #8768. Arrested Development | wuxman57 | TL | 60ms | 14312kb | Python3 | 470b | 2024-08-19 03:10:32 | 2024-08-19 03:10:32 |
Judging History
answer
n = int(input())
a = [0] * n
b = [0] * n
maxval = 0
for x in range(0, n):
line = [int(i) for i in input().split(" ")]
a[x] = line[0]
b[x] = line[1]
maxval += a[x]
dp = [float("inf")] * (maxval + 1)
dp[0] = 0
for x in range(0, n):
for y in range(maxval, -1, -1):
dp[y] += b[x]
if y >= a[x]:
dp[y] = min(dp[y], dp[y - a[x]])
ans = float("inf")
for x in range(0, maxval + 1):
ans = min(ans, max(x, dp[x]))
print(ans)
詳細信息
Test #1:
score: 100
Accepted
time: 10ms
memory: 10708kb
input:
4 100 1 1 90 1 20 1 20
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 16ms
memory: 10740kb
input:
2 314 1 592 6
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 16ms
memory: 10700kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 60ms
memory: 14308kb
input:
1 100000 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 15ms
memory: 10636kb
input:
1 1 100000
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 46ms
memory: 14312kb
input:
1 100000 100000
output:
100000
result:
ok single line: '100000'
Test #7:
score: -100
Time Limit Exceeded
input:
50 78681 95291 22639 1538 12119 52253 50430 63757 66133 92826 61048 40069 33506 30382 96049 50134 42895 62735 86943 16955 9667 61843 49647 9320 29082 16909 69601 68436 19892 34306 29822 79462 73262 14568 1693 35040 89757 61888 56993 48750 89611 77773 54159 21067 32520 41091 52501 92770 36530 17589 5...