結果
問題 | No.616 へんなソート |
ユーザー |
👑 |
提出日時 | 2021-06-10 22:23:05 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 826 bytes |
コンパイル時間 | 241 ms |
コンパイル使用メモリ | 6,948 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 09:27:56 |
合計ジャッジ時間 | 1,692 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
local mod = 1000000007local function badd(a, b) return (a + b) % mod endlocal function bsub(x, y)return x < y and x - y + mod or x - yendlocal n, k = io.read("*n", "*n", "*l")io.read()local dp1, dp2 = {}, {}for i = 1, k + 1 dodp1[i] = 0enddp1[1] = 1local dstlim = 1for i = 1, n dodstlim = dstlim + i - 1local src = i % 2 == 1 and dp1 or dp2local dst = i % 2 == 1 and dp2 or dp1for j = 1, dstlim dodst[j] = 0endfor srcpos = 1, dstlim - i + 1 dodst[srcpos] = badd(dst[srcpos], src[srcpos])if srcpos + i - 1 < dstlim thendst[srcpos + i] = bsub(dst[srcpos + i], src[srcpos])endendfor j = 2, dstlim dodst[j] = badd(dst[j], dst[j - 1])endendlocal tbl = n % 2 == 1 and dp2 or dp1local ret = 0for i = 1, k + 1 doret = badd(ret, tbl[i])endprint(ret)