結果
問題 | No.1536 仕切り直し |
ユーザー |
|
提出日時 | 2022-10-08 09:09:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 204 ms / 2,000 ms |
コード長 | 811 bytes |
コンパイル時間 | 140 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 122,208 KB |
最終ジャッジ日時 | 2024-06-22 07:20:08 |
合計ジャッジ時間 | 2,048 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 |
ソースコード
N, M = map(int, input().split())A = map(int, input().split())def sign(x):return -1 if (x & 1) else 1dp = [[-10 ** 18] * (M + 1) for _ in range(N + 1)]partition_flag = [[False] * (M + 1) for _ in range(N + 1)]for j in range(M + 1):dp[0][j] = 0for i, a in enumerate(A):for j in range(min(i + 1, M + 1)):dp[i + 1][j] = dp[i][j] + sign(j) * afor j in range(1, M + 1):if dp[i + 1][j] < dp[i][j - 1] + sign(j) * a:partition_flag[i + 1][j] = Truedp[i + 1][j] = dp[i][j - 1] + sign(j) * a# 復元max_index = dp[N].index(max(dp[N]))ans = []j = max_indexfor i in range(N, 0, -1):if partition_flag[i][j]:ans.append(i - 1)j -= 1assert j >= 0ans.reverse()ans.extend([N] * (M - len(ans)))print(*ans, sep="\n")