結果
問題 | No.710 チーム戦 |
ユーザー | 👑 obakyan |
提出日時 | 2022-10-26 22:56:52 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 828 ms / 3,000 ms |
コード長 | 974 bytes |
コンパイル時間 | 61 ms |
コンパイル使用メモリ | 5,376 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-07-04 11:00:36 |
合計ジャッジ時間 | 13,760 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
local n = io.read("*n")local a, b = {}, {}local asum = 0for i = 1, n doa[i], b[i] = io.read("*n", "*n")asum = asum + a[i]endlocal function solve(x)local need = asum - xlocal t = {}for i = 1, need - 1 dot[i] = falseendlocal ans = falsefor i = 1, n dolocal ai, bi = a[i], b[i]for j = need - 1, 1, -1 doif t[j] thenif need <= j + ai thenif not ans or t[j] + bi < ans thenans = t[j] + biendelseif not t[j + ai] or t[j] + bi < t[j + ai] thent[j + ai] = t[j] + biendendendendif ai < need thenif not t[ai] or bi < t[ai] then t[ai] = bi endelseif not ans or bi < ans then ans = bi endendendreturn ans and ans <= xendlocal min, max = 0, asumwhile 1 < max - min dolocal mid = math.floor((min + max) / 2)if solve(mid) thenmax = midelsemin = midendendprint(max)