問題概要
問題ページ
-
-
D - Static Sushi
問題ページへ移動する
問題文
日本料理店「停止寿司」は円形のカウンターが一つあるだけのシンプルな店です。カウンターの外周の長さは \(C\) メートルで、カウンターの内部に客が立ち入ることはできません。
中橋くんが入店し、カウンターのそばまで案内されました。いま、カウンター上には \(N\) 貫の寿司が置かれています。そのうち \(i\) 貫目は中橋くんがいる位置から \(x_i\) メートル時計回りに進んだ位置に置かれており、\(v_i\) キロカロリーの栄養価を持ちます。
中橋くんはカウンターの外周を自由に歩き回ることができます。寿司が置かれている位置にたどり着いたら、その寿司を食べて寿司が持つ栄養価を摂取することができます（当然、その寿司は消えます）。ただし、歩く際に \(1\) メートルあたり \(1\) キロカロリーを消費します。
満足したら、いつでも好きな位置から店を出ることができます（始めにいた位置に戻らなくても構いません）。店を出るまでに最大で差し引き何キロカロリーを摂取することができるでしょうか？すなわち、退店するまでに摂取した栄養価の合計から消費したエネルギーを引いた値の最大値はいくらでしょうか？なお、他に客はおらず、新たな寿司がカウンターに追加されることもないものとします。また、中橋くんは十分な栄養を蓄えているため、どれだけ歩いてエネルギーを消費しても餓死しないものとします。
制約
- \(1 ≤ N ≤ 10^5\)
- \(2 ≤ C ≤ 10^{14}\)
- \(1 ≤ x_1 < x_2 < ... < x_N < C\)
- \(1 ≤ v_i ≤ 10^9\)
- 入力中のすべての値は整数である。
部分点
- \(N ≤ 100\) を満たすテストセットに正解すると、\(300\) 点が与えられる。
問題の考察
ACコード
import sys
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n, c = list(map(int, input().rstrip('\n').split()))
xy = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
f_cost = xy[0][0]
f_energy = xy[0][1]
f = [[f_cost, f_energy, f_energy - f_cost]]
b_cost = c - xy[-1][0]
b_energy = xy[-1][1]
b = [[b_cost, b_energy, b_energy - b_cost]]
for i in range(1, n):
f_cost += xy[i][0] - xy[i-1][0]
f_energy += xy[i][1]
f.append([f_cost, f_energy, max(f_energy - f_cost, f[-1][2])])
b_cost += xy[-i][0] - xy[-i-1][0]
b_energy += xy[-i-1][1]
b.append([b_cost, b_energy, max(b_energy - b_cost, b[-1][2])])
mx = 0
for i in range(n):
mx = max(mx, f[i][2], b[i][2])
if n - i - 2 >= 0:
mx = max(mx, f[i][2] - f[i][0] + b[n - i - 2][2], b[i][2] - b[i][0] + f[n - i - 2][2])
print(mx)
if __name__ == '__main__':
solve()