Submission #27849

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
m = int(input())
jam = []
for i in range(m):
jam.append(int(input()))
w_hate_max = [[] for _ in range(m)]
for i in range(5):
kind_i, w_i, hate_i, max_in_i = map(int, input().split())
kind_i -= 1
w_hate_max[kind_i].append([w_i, hate_i, max_in_i])
total = 0
for i in range(m):
infinity = 1000000000
n = len(w_hate_max[i])
dp = [[infinity] * (jam[i] + 1) for _ in range(n + 1)]
dp[0][0] = 0
for j in range(n):
w, hate, max_in = w_hate_max[i][j]
for picked in range(w + 1):
dissatisfaction = 0 if picked == w else 4 << (w - picked + hate)
if dissatisfaction > max_in:
continue
for k in range(picked, jam[i] + 1):
dp[j + 1][k] = min(
dp[j + 1][k],
dp[j][k - picked] + dissatisfaction)
minimum = infinity
for k in range(jam[i] + 1):
minimum = min(minimum, dp[n][k])
if minimum == infinity:
total = 'Hello!'
break
else:
total += minimum
print(total)

ステータス

項目 データ
問題 0016 - ありすぬーんてぃー
ユーザー名 KirikaYuumura
投稿日時 2017-10-25 15:22:33
言語 Python3
状態 Accepted
得点 35
ソースコード長 1093 Byte
最大実行時間 47 ms
最大メモリ使用量 4268 KB

セット

セット 得点 Cases
1 ALL 35 / 35 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
Alice_in1.txt AC 47 ms 4104 KB
1
Alice_in2.txt AC 35 ms 4172 KB
1
Alice_in3.txt AC 47 ms 4248 KB
1
Alice_in4.txt AC 39 ms 4192 KB
1
Alice_in5.txt AC 35 ms 4268 KB
1