結果

問題 No.1297 銅像
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:32:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,445 bytes
コンパイル時間 499 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 89,768 KB
最終ジャッジ日時 2025-06-12 13:39:20
合計ジャッジ時間 5,045 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, C = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

L = [0] * (n + 1)  # 1-based indexing for craftsmen
R = [0] * (n + 1)

for k in range(1, n + 1):
    # Find L_k (smallest x where craftsman k can cover x)
    low, high = 1, k
    left = k
    while low <= high:
        mid = (low + high) // 2
        if a[k-1] + C * (k - mid) <= a[mid-1] + b[mid-1]:
            left = mid
            high = mid - 1
        else:
            low = mid + 1
    L[k] = left

    # Find R_k (largest x where craftsman k can cover x)
    low, high = k, n
    right = k
    while low <= high:
        mid = (low + high) // 2
        if a[k-1] + C * (mid - k) <= a[mid-1] + b[mid-1]:
            right = mid
            low = mid + 1
        else:
            high = mid - 1
    R[k] = right

INF = float('inf')
dp = [INF] * (n + 2)
dp[0] = 0

# Update dp for individual assignments
for x in range(1, n + 1):
    cost = b[x-1] + a[x-1]
    if dp[x-1] + cost < dp[x]:
        dp[x] = dp[x-1] + cost

# Update dp for each craftsman's optimal interval
for k in range(1, n + 1):
    l = L[k]
    r = R[k]
    if l > r:
        continue
    m = r - l + 1
    sum_dist = (k - l) * (k - l + 1) // 2 + (r - k) * (r - k + 1) // 2
    total_cost = b[k-1] + m * a[k-1] + C * sum_dist
    if l - 1 >= 0 and dp[l-1] + total_cost < dp[r]:
        dp[r] = dp[l-1] + total_cost

print(dp[n])
0