結果
問題 | No.45 回転寿司 |
ユーザー | mega_yadoran |
提出日時 | 2018-10-22 15:20:49 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,403 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 94,592 KB |
最終ジャッジ日時 | 2024-04-29 20:34:41 |
合計ジャッジ時間 | 13,486 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 592 ms
84,096 KB |
testcase_01 | AC | 1,529 ms
81,536 KB |
testcase_02 | AC | 3,992 ms
88,320 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 1,828 ms
82,560 KB |
testcase_05 | AC | 75 ms
73,728 KB |
testcase_06 | AC | 1,078 ms
80,384 KB |
testcase_07 | AC | 3,850 ms
87,936 KB |
testcase_08 | AC | 220 ms
77,184 KB |
testcase_09 | AC | 4,423 ms
88,832 KB |
testcase_10 | AC | 655 ms
78,464 KB |
testcase_11 | AC | 181 ms
76,672 KB |
testcase_12 | AC | 4,242 ms
88,832 KB |
testcase_13 | AC | 69 ms
70,656 KB |
testcase_14 | AC | 59 ms
63,744 KB |
testcase_15 | AC | 838 ms
79,360 KB |
testcase_16 | AC | 289 ms
77,312 KB |
testcase_17 | AC | 571 ms
78,464 KB |
testcase_18 | AC | 316 ms
77,440 KB |
testcase_19 | AC | 3,822 ms
85,120 KB |
testcase_20 | AC | 57 ms
63,232 KB |
testcase_21 | AC | 66 ms
68,608 KB |
testcase_22 | AC | 42 ms
51,584 KB |
testcase_23 | AC | 41 ms
51,968 KB |
testcase_24 | AC | 42 ms
51,968 KB |
testcase_25 | AC | 41 ms
51,840 KB |
testcase_26 | AC | 787 ms
79,488 KB |
testcase_27 | AC | 2,810 ms
85,632 KB |
testcase_28 | AC | 987 ms
80,128 KB |
testcase_29 | AC | 2,210 ms
83,968 KB |
testcase_30 | AC | 2,438 ms
84,608 KB |
testcase_31 | AC | 41 ms
52,096 KB |
testcase_32 | AC | 41 ms
51,712 KB |
testcase_33 | TLE | - |
ソースコード
# !/bin/python # this code tested Python3.6+ """ 入力: N V1 V2 V3 …VN 例: 4 1 2 3 4 で入力された寿司の美味しさで、 皿を取ったら、2個目は1回開けなければならないとき、 美味しさの最大となる組み合わせを探せ。 上記の例なら、2 + 4 で 6 (2 を取ったので 3 は取れない) """ memories = {} # メモ化キャッシュ def select(index, scores): """scores から指定のインデックス要素と、その後ろを取得する。 ※ただし、後ろ部分に関しては、問題の定義より一つ以上空白をあける。 """ tail_head_index = index + 2 head = scores[index] if len(scores) <= tail_head_index: return (head, []) else: return (head, scores[tail_head_index:]) def max_score(scores): """scores で渡した点数リストから、最大スコアの組み合わせを計算する。 ただし、選択したスコアから、次のスコアを選ぶときには、 一つ以上隙間を用意しなければならない。 Arguments: scores {list} -- スコアリスト Returns: int -- そのリストから計算できる最大スコア """ tupled = tuple(scores) if tupled in memories: # キャッシュ済みならキャッシュから返す #print('Cache HIT!') return memories.get(tupled) list_length = len(scores) if list_length == 1: # 要素が一つならその値を返す memories[tupled] = scores[0] return scores[0] # 今の scores 内での最大取得可能スコアを計算 cur_score = 0 for i in range(0, list_length): # N 番目要素を順に取得して試す。 tmp_score, tail = select(i, scores) # 後ろの要素があるなら、その最大スコアを加算 if len(tail) > 0: tmp_score = tmp_score + max_score(tail) # 現在計算しているスコアが大きければ置き換える cur_score = tmp_score if cur_score <= tmp_score else cur_score # スコアをキャッシュしてリターン memories[tupled] = cur_score return cur_score if __name__ == '__main__': N = int(input()) # リストサイズ SCORES = [int(v) for v in input().split(' ')] # 寿司おいしさリスト print(max_score(SCORES))