結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
👑 ![]() |
提出日時 | 2019-07-11 01:57:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,461 ms / 2,000 ms |
コード長 | 789 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 80,256 KB |
最終ジャッジ日時 | 2024-06-11 13:56:16 |
合計ジャッジ時間 | 12,476 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
INF = 0x1fffffffffffffff def priority(a): return a if a & 1 else INF - a n = int(input()) dp = [INF] * (n + 1) mn = [INF] * (n + 1) mx = [-INF] * (n + 1) dp[0] = 0 for i in range(n): j = 1 while i + j * j <= n: if dp[i + j * j] > dp[i] + j: dp[i + j * j] = dp[i] + j mn[i + j * j] = j mx[i + j * j] = j elif(dp[i + j * j] == dp[i] + j): if priority(mn[i + j * j]) > priority(j): mn[i + j * j] = j if priority(mx[i + j * j]) < priority(j): mx[i + j * j] = j j += 1 c = 48 ans = "" while n: cnt = mn[n] if c == 48 else mx[n] n -= cnt * cnt; for i in range(cnt): ans += chr(c) c ^= 1 c ^= 1; print(ans)