Problem:
 Score : 100 points    Problem Statement In a long narrow forest stretching east-west, there are N beasts. Below, we will call the point that is p meters from the west end Point p . The i -th beast from the west (1 ≤ i ≤ N) is at Point x_i , and can be sold for s_i yen (the currency of Japan) if captured.  You will choose two integers L and R  (L ≤ R) , and throw a net to cover the range from Point L to Point R including both ends, [L, R] . Then, all the beasts in the range will be captured. However, the net costs R - L yen and your profit will be ( the sum of s_i over all captured beasts i) - (R - L) yen.  What is the maximum profit that can be earned by throwing a net only once?      Constraints  1 ≤ N ≤ 2 × 10^5  1 ≤ x_1 < x_2 < ... < x_N ≤ 10^{15}  1 ≤ s_i ≤ 10^9  All input values are integers.         Input Input is given from Standard Input in the following format:  N  x_1  s_1  x_2  s_2  :  x_N  s_N       Output When the maximum profit is X yen, print the value of X .        Sample Input 1 5
10 20
40 50
60 30
70 40
90 10      Sample Output 1 90  If you throw a net covering the range [L = 40, R = 70] , the second, third and fourth beasts from the west will be captured, generating the profit of s_2 + s_3 + s_4 - (R - L) = 90 yen. It is not possible to earn 91 yen or more.       Sample Input 2 5
10 2
40 5
60 3
70 4
90 1      Sample Output 2 5  The positions of the beasts are the same as Sample 1, but the selling prices dropped significantly, so you should not aim for two or more beasts. By throwing a net covering the range [L = 40, R = 40] , you can earn s_2 - (R - L) = 5 yen, and this is the maximum possible profit.       Sample Input 3 4
1 100
3 200
999999999999999 150
1000000000000000 150      Sample Output 3 299

Solution (Python):
from itertools import accumulate
n = int(input())
XS = tuple(tuple(map(int, input().split())) for _ in range(n))
X, S = zip(*XS)
A = tuple(accumulate(S))
B = tuple(a-x for x, a in zip(X, A))
A = [0] + list(A)
X = list(X) + [0]
C = tuple(a-x for x, a in zip(X, A))[:-1]
m = float("inf")
ans = 0
for b, c in zip(B, C):
  m = min(m, c)
  ans = max(ans, b-m)
print(ans)

Solution (Python):
n=int(input())

x=[]
s=[]
for i in range(n):
    p,q=map(int,input().split())
    x.append(p)
    s.append(q)
r=[0]
for i in range(n):
    r.append(r[-1]+s[i])
b=[]
for i in range(n):
    b.append(r[i+1]-x[i])
a=[-10**30]*n
a[-1]=b[-1]
for i in range(n-1):
    a[n-i-2]=max(a[n-i-1],b[n-i-2])

ans=0
for i in range(n):
    ans=max(ans,a[i]-(r[i]-x[i]))
print(ans)

Solution (Python):
n=int(input())

x=[]
s=[]
for i in range(n):
    p,q=map(int,input().split())
    x.append(p)
    s.append(q)
r=[0]
for i in range(n):
    r.append(r[-1]+s[i])
b=[]
for i in range(n):
    b.append(r[i+1]-x[i])
a=[-10**30]*n
a[-1]=b[-1]
for i in range(n-1):
    a[n-i-2]=max(a[n-i-1],b[n-i-2])

ans=0
for i in range(n):
    ans=max(ans,a[i]-(r[i]-x[i]))
print(ans)

Solution (Python):


def segfunc(x,y):
    return max(x,y)

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=-10**30
n=int(input())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
x=[]
s=[]
for i in range(n):
    p,q=map(int,input().split())
    x.append(p)
    s.append(q)
r=[0]
for i in range(n):
    r.append(r[-1]+s[i])
b=[]
for i in range(n):
    b.append(r[i+1]-x[i])
init(b)
ans=0
for i in range(n):
    ans=max(ans,query(i,n)-(r[i]-x[i]))
print(ans)

Solution (Python):
from itertools import accumulate as ac
n=int(input())
a,b=[],[]
for i in range(n):
    x,s=map(int,input().split())
    a.append(x)
    b.append(s)
r=[0]+list(ac(b))
l=r[:]
for i in range(n):
    r[i]+=-a[i]
    l[i+1]+=-a[i]
q,d=r[0],0
for i in range(1,n+1):
    d=max(l[i]-q,d)
    q=min(q,r[i])
print(d)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
XS = np.array(read().split(),np.int64)

"""
・右端を固定するごとに考える
・左端まで全部とる状態を基準点とする
・x座標：xの節約
・sの累積和：諦めるs
"""

X = XS[::2]; S = XS[1::2]

Scum = S.cumsum()

x = X.copy()
x[1:] -= Scum[:-1]

answer = (-X+Scum+np.maximum.accumulate(x)).max()
print(answer)

Solution (Python):
N = int(input())
xs, ss = [], []
for _ in range(N):
    x, s = map(int, input().split())
    xs.append(x)
    ss.append(s)

As = [ss[0]]
for i in range(1, N):
    As += [-(xs[i]-xs[i-1]), ss[i]]

accA = 0
ans = 0
for A in As:
    accA += A
    if accA < 0:
        accA = 0
    ans = max(ans, accA)

print(ans)

Solution (Python):
n = int(input())
ans = 0
tmp = 0
prev = 0
for x, s in (map(int, input().split()) for _ in range(n)):
    dx = x - prev
    if dx > tmp:
        tmp = s
    else:
        tmp += s - dx
    ans = max(ans, tmp)
    prev = x
ans = max(ans, tmp)
print(ans)

Solution (Python):
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]

cum_r = [src[0][1]]
for (x1,s1),(x2,s2) in zip(src,src[1:]):
    gain = s2 - (x2 - x1)
    cum_r.append(cum_r[-1] + gain)

best_l = [0]
for (x,s),c in list(zip(src, cum_r))[1::]:
    best_l.append(max(best_l[-1], s - c))

ans = 0
for l,r in zip(best_l, cum_r):
    ans = max(ans, l+r)
print(ans)

Solution (Python):
N = int(input())
A = 0; p = 0
ans = 0
for i in range(N):
    x, s = map(int, input().split())
    A = max(0, A - (x - p)) + s
    ans = max(ans, A)
    p = x
print(ans)