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



Sample input:
5
10 20
40 50
60 30
70 40
90 10


Sample output:
90

Submission status: Wrong Answer

Solution code:
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-1])
print(d)

Submission status: Wrong Answer

Solution code:
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=0,0
for i in range(1,n+1):
    d=max(l[i]-q,d)
    q=min(q,r[i-1])
print(d)

Submission status: Wrong Answer

Solution code:
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=0,0
for i in range(1,n+1):
    d=max(l[i]-q,d)
    q=min(q,r[i])
print(d)

Submission status: Wrong Answer

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

r_cumsum = [src[-1][1]]
r_cummax = [src[-1][1]]
for (x1,s1),(x2,s2) in reversed(list(zip(src, src[1:]))):
    r_cumsum.append(r_cumsum[-1] + s1 - (x2 - x1))
    r_cummax.append(max(r_cummax[-1], r_cumsum[-1]))
r_cumsum.reverse()
r_cummax.reverse()

ans = 0
for (x,s),c in zip(src, r_cummax):
    tmp = s + r_cummax[0] - c
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

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

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:
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=b[:]
for i in range(n):
    r[i]+=-a[i]
    l[i+1]+=-a[i]
q,d=0,0
for i in range(1,n+1):
    d=max(l[i]-q,d)
    q=min(q,r[i-1])
print(d)