結果

問題 No.1715 Dinner 2
ユーザー lam6er
提出日時 2025-03-31 17:37:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,279 ms / 2,000 ms
コード長 2,434 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 79,128 KB
最終ジャッジ日時 2025-03-31 17:38:42
合計ジャッジ時間 14,412 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
def main():
    sys.setrecursionlimit(1 << 25)
    N, D = map(int, sys.stdin.readline().split())
    dishes = []
    for _ in range(N):
        P, Q = map(int, sys.stdin.readline().split())
        dishes.append((P, Q))

    # Binary search boundaries
    low = -10**18
    high = 10**18
    answer = low

    def check(X):
        dp_prev = [-10**18] * N
        # Initialize day 1
        for j in range(N):
            Pj, Qj = dishes[j]
            step1 = 0 - Pj
            step2 = step1 + Qj
            if step1 >= X and step2 >= X:
                dp_prev[j] = step2
            else:
                dp_prev[j] = -10**18

        if D == 1:
            return any(val != -10**18 for val in dp_prev)

        for d in range(2, D+1):
            current_dp = [-10**18] * N
            # Precompute max values
            max_val = max(dp_prev)
            if max_val == -10**18:
                return False
            second_max = -10**18
            count_max = 0
            best_j = -1
            for j in range(N):
                if dp_prev[j] == max_val:
                    count_max += 1
                    best_j = j
                elif dp_prev[j] > second_max and dp_prev[j] < max_val:
                    second_max = dp_prev[j]

            for i in range(N):
                Ti = max(X + dishes[i][0], X + (dishes[i][0] - dishes[i][1]))
                if max_val < Ti:
                    continue  # even max_val is less than Ti, no way
                # Compute max_without_i
                if count_max > 1:
                    max_without_i = max_val
                else:
                    if best_j == i:
                        max_without_i = second_max
                    else:
                        max_without_i = max_val
                if max_without_i < Ti:
                    continue
                # compute new_E
                new_E = max_without_i - dishes[i][0] + dishes[i][1]
                current_dp[i] = new_E
            dp_prev = current_dp
            # Early termination if all current_dp are -inf
            if all(val == -10**18 for val in dp_prev):
                return False
        # After D days
        return any(val != -10**18 for val in dp_prev)

    while low < high:
        mid = (low + high + 1) // 2
        if check(mid):
            low = mid
        else:
            high = mid - 1
    print(low)

if __name__ == "__main__":
    main()
0