結果
問題 | No.489 株に挑戦 |
ユーザー |
👑 |
提出日時 | 2019-05-02 15:25:08 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 94 ms / 1,000 ms |
コード長 | 1,711 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 5,376 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 00:13:31 |
合計ジャッジ時間 | 2,478 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
local ior = io.input()local n, d, k = ior:read("*n", "*n", "*n")local t = {}for i = 1, n do t[i] = ior:read("*n") endlocal ret_stt_pos = 1local ret_val = 0local mma, mmi, mce = math.max, math.min, math.ceilif(d < 50) thenfor i = 1, n - 1 dolocal max = 0local lst = mmi(n, i + d)for j = i + 1, lst domax = mma(max, t[j])endif(ret_val < max - t[i]) thenret_val = max - t[i]ret_stt_pos = iendendelselocal sqd = math.floor(math.sqrt(d))local blockmax = {}local blockcount = mce(n / sqd)for i = 1, blockcount do blockmax[i] = 0 endfor i = 1, n dolocal b_idx = mce(i / sqd)blockmax[b_idx] = mma(blockmax[b_idx], t[i])endfor i = 1, n - 1 dolocal max = 0local lst = mmi(n, i + d)local block_start_idx = mce(i / sqd) + 1local block_end_idx = mce(lst / sqd) - 1local block_start_pos = (block_start_idx - 1) * sqd + 1block_start_pos = mmi(n + 1, block_start_pos)local block_end_pos = block_end_idx * sqdfor j = block_start_idx, block_end_idx domax = mma(max, blockmax[j])endfor j = i + 1, block_start_pos - 1 domax = mma(max, t[j])endif(block_start_idx <= block_end_idx) thenfor j = block_end_pos + 1, lst domax = mma(max, t[j])endendif(ret_val < max - t[i]) thenret_val = max - t[i]ret_stt_pos = iendendendprint(ret_val * k)if(0 < ret_val) thenlocal max = t[ret_stt_pos + 1]local maxj = ret_stt_pos + 1local lst = mmi(n, ret_stt_pos + d)for j = ret_stt_pos + 1, lst doif(max < t[j]) thenmax, maxj = t[j], jendendprint(ret_stt_pos - 1 .. " " .. maxj - 1)end