結果
問題 | No.625 ソンタクロース |
ユーザー | matsu7874 |
提出日時 | 2017-12-24 16:22:08 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 225 ms / 4,000 ms |
コード長 | 1,142 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 10,968 KB |
実行使用メモリ | 16,160 KB |
最終ジャッジ日時 | 2023-08-22 18:05:38 |
合計ジャッジ時間 | 2,205 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 15 ms
8,124 KB |
testcase_01 | AC | 15 ms
7,716 KB |
testcase_02 | AC | 16 ms
7,784 KB |
testcase_03 | AC | 16 ms
8,112 KB |
testcase_04 | AC | 16 ms
8,132 KB |
testcase_05 | AC | 15 ms
8,316 KB |
testcase_06 | AC | 15 ms
8,228 KB |
testcase_07 | AC | 14 ms
8,272 KB |
testcase_08 | AC | 14 ms
8,164 KB |
testcase_09 | AC | 14 ms
8,172 KB |
testcase_10 | AC | 15 ms
8,124 KB |
testcase_11 | AC | 14 ms
7,828 KB |
testcase_12 | AC | 15 ms
8,220 KB |
testcase_13 | AC | 15 ms
8,164 KB |
testcase_14 | AC | 15 ms
8,276 KB |
testcase_15 | AC | 31 ms
8,820 KB |
testcase_16 | AC | 21 ms
8,628 KB |
testcase_17 | AC | 103 ms
11,364 KB |
testcase_18 | AC | 225 ms
16,160 KB |
testcase_19 | AC | 44 ms
9,360 KB |
testcase_20 | AC | 46 ms
9,376 KB |
testcase_21 | AC | 30 ms
8,828 KB |
testcase_22 | AC | 184 ms
14,648 KB |
testcase_23 | AC | 27 ms
8,828 KB |
ソースコード
def main(n, m): gain = [[0] * n for i in range(n)] for i in range(n): for j in range(i): gain[i][j] = -1 gain[n - 1][n - 1] = m for i in range(n - 2, -1, -1): santa = [] for j in range(i + 1, n): santa.append((gain[i + 1][j], -j)) santa.sort(reverse=True) majority = (n - i) // 2 + 1 rest = m vote = 1 for j in range(majority - 1): g, si = santa.pop() si = -si if rest >= g+1: vote += 1 gain[i][si] = g+1 rest -= gain[i][si] if vote*2 > n-i: gain[i][i] = rest else: gain[i][i] = -1 for j in range(i+1, n): gain[i][j] = gain[i+1][j] # 実現する結果を探す for i in range(n-1): vote = 0 for j in range(n): if gain[i][j] > gain[i+1][j]: vote += 1 if vote * 2 > n-i: return gain[i] return gain[n-1] if __name__ == '__main__': SANTA, PRESENT = map(int, input().split()) print(*main(SANTA, PRESENT))