結果
問題 |
No.2370 He ate many cakes
|
ユーザー |
|
提出日時 | 2024-01-22 01:27:58 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,651 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 77,952 KB |
最終ジャッジ日時 | 2024-09-28 06:18:28 |
合計ジャッジ時間 | 2,383 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 WA * 2 |
ソースコード
## https://yukicoder.me/problems/no/2370 def solve(n1_array, n2_array, border): ans = 0 for n2 in n2_array: if border - n2 > n1_array[-1]: continue low = 0 high = len(n1_array) - 1 while high - low > 1: mid = (high + low) // 2 if n1_array[mid] >= border - n2: high = mid else: low = mid if n1_array[low] >= border - n2: ans += len(n1_array) - low else: ans += len(n1_array) - high return ans def main(): N, K = map(int, input().split()) A = list(map(int, input().split())) if N == 1: array = [0, A[0]] array.sort() print(array[K - 1]) return # 半分全列挙 N1 = N // 2 N2 = N - N1 n1_array = [] for bit in range(2 ** N1): ans = 0 for i in range(N1): if bit & (1 << i) > 0: ans += A[i] n1_array.append(ans) n1_array.sort() n2_array = [] for bit in range(2 ** N2): ans = 0 for i in range(N2): if bit & (1 << i) > 0: ans += A[i + N1] n2_array.append(ans) # 二部探索によって値を出す low = sum([a for a in A if a < 0]) high = sum([a for a in A if a > 0]) while high - low > 1: mid = (high + low) // 2 if solve(n1_array, n2_array, mid) >= K: low = mid else: high = mid if solve(n1_array, n2_array, high) >= K: print(high) else: print(low) if __name__ == "__main__": main()