Problem:


Score : 1000 points

Problem Statement

There are N barbecue restaurants along a street.
The restaurants are numbered 1 through N from west to east, and the distance between restaurant i and restaurant i+1 is A_i.

Joisino has M tickets, numbered 1 through M.
Every barbecue restaurant offers barbecue meals in exchange for these tickets.
Restaurant i offers a meal of deliciousness B_{i,j} in exchange for ticket j.
Each ticket can only be used once, but any number of tickets can be used at a restaurant.

Joisino wants to have M barbecue meals by starting from a restaurant of her choice, then repeatedly traveling to another barbecue restaurant and using unused tickets at the restaurant at her current location.
Her eventual happiness is calculated by the following formula: "(The total deliciousness of the meals eaten) - (The total distance traveled)".
Find her maximum possible eventual happiness.

Constraints

All input values are integers.

2≤N≤5×10^3

1≤M≤200

1≤A_i≤10^9

1≤B_{i,j}≤10^9

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_{N-1}
B_{1,1} B_{1,2} ... B_{1,M}
B_{2,1} B_{2,2} ... B_{2,M}
:
B_{N,1} B_{N,2} ... B_{N,M}

Output

Print Joisino's maximum possible eventual happiness.

Sample Input 1

3 4
1 4
2 2 5 1
1 3 3 2
2 2 5 1

Sample Output 1

11

The eventual happiness can be maximized by the following strategy: start from restaurant 1 and use tickets 1 and 3, then move to restaurant 2 and use tickets 2 and 4.

Sample Input 2

5 3
1 2 3 4
10 1 1
1 1 1
1 10 1
1 1 1
1 1 10

Sample Output 2

20



Sample input:
3 4
1 4
2 2 5 1
1 3 3 2
2 2 5 1


Sample output:
11

Submission status: Memory Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import gc

def main():

    n,m = map(int,readline().split())
    a = list(map(int,readline().split()))
    a += [0,0,0]
    b = []
    b = [list(map(int,i.split())) for i in  readlines()]

    gc.collect()

    imos = [[0] * (n+2) for _ in range(n+2)]
    left = [0] * (n+2)
    right = [0] * (n+2)
    bi = [[0,0] for _ in range(n)]

    for i in range(m):
        if(i%400==0):
            gc.collect()
        for j in range(n+2):
            left[j] = j-1
            right[j] = j+1

        for j in range(n):
            bi[j][0] = b[j][i]
            bi[j][1] = j+1
        bi.sort()
        for val,j in bi:
            l = left[j]
            r = right[j]
            imos[l+1][j] += val
            imos[l+1][r] -= val
            imos[j+1][j] -= val
            imos[j+1][r] += val
            right[l] = r
            left[r] = l

    for i in range(n+1):
        for j in range(1,n+1):
            imos[i][j] += imos[i][j-1]

    for i in range(1,n+1):
        for j in range(n+1):
            imos[i][j] += imos[i-1][j]

    ans = 0
    for i in range(1,n+1):
        dif = 0
        for j in range(i,n+1):
            ans = max(ans,imos[i][j] - dif)
            dif += a[j-1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import gc

def main():

    n,m = map(int,readline().split())
    a = list(map(int,readline().split()))
    a += [0,0,0]
    b = []
    for _ in range(n):
        b += list(map(int,readline().split()))

    gc.collect()

    imos = [[0] * (n+2) for _ in range(n+2)]
    left = [0] * (n+2)
    right = [0] * (n+2)
    bi = [[0,0] for _ in range(n)]

    for i in range(m):
        if(i%400==0):
            gc.collect()
        for j in range(n+2):
            left[j] = j-1
            right[j] = j+1

        for j in range(n):
            bi[j][0] = b[i+j*m]
            bi[j][1] = j+1
        bi.sort()
        for val,j in bi:
            l = left[j]
            r = right[j]
            imos[l+1][j] += val
            imos[l+1][r] -= val
            imos[j+1][j] -= val
            imos[j+1][r] += val
            right[l] = r
            left[r] = l

    for i in range(n+1):
        for j in range(1,n+1):
            imos[i][j] += imos[i][j-1]

    for i in range(1,n+1):
        for j in range(n+1):
            imos[i][j] += imos[i-1][j]

    ans = 0
    for i in range(1,n+1):
        dif = 0
        for j in range(i,n+1):
            ans = max(ans,imos[i][j] - dif)
            dif += a[j-1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import gc

def main():

    n,m = map(int,readline().split())
    a = list(map(int,readline().split()))
    a += [0,0,0]
    b = list(map(int,read().split()))

    imos = [[0] * (n+2) for _ in range(n+2)]
    left = [0] * (n+2)
    right = [0] * (n+2)
    bi = [[0,0] for _ in range(n)]

    gc.collect()

    for i in range(m):
        for j in range(n+2):
            left[j] = j-1
            right[j] = j+1

        for j in range(n):
            bi[j][0] = b[i+j*m]
            bi[j][1] = j+1
        bi.sort()
        for val,j in bi:
            l = left[j]
            r = right[j]
            imos[l+1][j] += val
            imos[l+1][r] -= val
            imos[j+1][j] -= val
            imos[j+1][r] += val
            right[l] = r
            left[r] = l

    for i in range(n+1):
        for j in range(1,n+1):
            imos[i][j] += imos[i][j-1]

    for i in range(1,n+1):
        for j in range(n+1):
            imos[i][j] += imos[i-1][j]

    ans = 0
    for i in range(1,n+1):
        dif = 0
        for j in range(i,n+1):
            ans = max(ans,imos[i][j] - dif)
            dif += a[j-1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():

    n,m = map(int,readline().split())
    a = list(map(int,readline().split()))
    a += [0,0,0]
    b = list(map(int,read().split()))

    imos = [[0] * (n+2) for _ in range(n+2)]
    left = [0] * (n+2)
    right = [0] * (n+2)
    bi = [[0,0] for _ in range(n)]

    for i in range(m):
        for j in range(n+2):
            left[j] = j-1
            right[j] = j+1

        for j in range(n):
            bi[j][0] = b[i+j*m]
            bi[j][1] = j+1
        bi.sort()
        for val,j in bi:
            l = left[j]
            r = right[j]
            imos[l+1][j] += val
            imos[l+1][r] -= val
            imos[j+1][j] -= val
            imos[j+1][r] += val
            right[l] = r
            left[r] = l

    for i in range(n+1):
        for j in range(1,n+1):
            imos[i][j] += imos[i][j-1]

    for i in range(1,n+1):
        for j in range(n+1):
            imos[i][j] += imos[i-1][j]

    ans = 0
    for i in range(1,n+1):
        dif = 0
        for j in range(i,n+1):
            ans = max(ans,imos[i][j] - dif)
            dif += a[j-1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
a += [0,0,0]
b = list(map(int,read().split()))

imos = [[0] * (n+2) for _ in range(n+2)]

for i in range(m):
    left = list(range(-1,n+1))
    right = list(range(1,n+3))

    bi = [(val,j) for j,val in enumerate(b[i::m], 1)]
    bi.sort()
    for val,j in bi:
        l = left[j]
        r = right[j]
        imos[l+1][j] += val
        imos[l+1][r] -= val
        imos[j+1][j] -= val
        imos[j+1][r] += val
        right[l] = r
        left[r] = l

for i in range(n+1):
    for j in range(1,n+1):
        imos[i][j] += imos[i][j-1]

for i in range(1,n+1):
    for j in range(n+1):
        imos[i][j] += imos[i-1][j]

ans = 0
for i in range(1,n+1):
    dif = 0
    for j in range(i,n+1):
        ans = max(ans,imos[i][j] - dif)
        dif += a[j-1]

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)
left_init = list(range(1,N))+[0,0]
right_init = list(range(-1,N))
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = left_init[:]
    right = right_init[:]
    for i in sorted(range(N), key=arr.__getitem__):
        l = left[i-1]
        r = right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
        if i<N-1 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

del B

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [0] + list(map(int, readline().split()))
for i in range(1, N):
    A[i] += A[i-1]

INF = 10**9+7
B = [list(map(int, readline().split())) for _ in range(N)] + [[INF]*M] + [[0]*M]
right = [[0]*M for _ in range(N)]

for m in range(M):
    L = list(range(N))
    L.sort(key = lambda x: B[x][m])
    RR = list(range(1, N+3))
    LL = list(range(-1, N+1))
    for vn in L:
        vn += 1
        right[vn-1][m] = RR[vn]-1
        RR[LL[vn]] = RR[vn]
        LL[RR[vn]] = LL[vn]

diff = [0]*(N+1)
for m in range(M):
    diff[0] += B[0][m]
    pre = B[0][m]
    for i in range(1, N):
        if B[i][m] > pre:
            diff[i] += B[i][m]-pre
            pre = B[i][m]

offset = 0
ans = 0
for l in range(N):
    offset += diff[l]
    for m in range(M):
        if B[l][m] < B[l-1][m]:
            oldr = right[l-1][m]
            diff[oldr] -= B[oldr][m] - B[l-1][m]
            offset += B[l][m] - B[l-1][m]
            cnt = l
            while cnt < N and right[cnt][m] <= oldr:
                rcm = right[cnt][m]
                diff[rcm] += B[rcm][m] - B[cnt][m]
                cnt = rcm
    ans = max(ans, offset)
    roff = offset
    for r in range(l+1, N):
        roff += diff[r]
        ans = max(ans, roff - (A[r]-A[l]))
        #print(l, r, roff - (A[r] - A[l]))

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import gc

def main():

    n,m = map(int,readline().split())
    a = list(map(int,readline().split()))
    a += [0,0,0]
    b = list(map(int,read().split()))

    imos = [[0] * (n+2) for _ in range(n+2)]
    left = [0] * (n+2)
    right = [0] * (n+2)
    bi = [[0,0] for _ in range(n)]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from array import array

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
a += [0,0,0]
b = list(map(int,read().split()))

# imos = [[0] * (n+2) for _ in range(n+2)]
imos = array('i', [0]*((n+2)**2))

for i in range(m):
    left = list(range(-1,n+1))
    right = list(range(1,n+3))

    bi = [(val,j) for j,val in enumerate(b[i::m], 1)]
    bi.sort()
    for val,j in bi:
        l = left[j]
        r = right[j]
        imos[(l+1)*(n+2)+j] += val
        imos[(l+1)*(n+2)+r] -= val
        imos[(j+1)*(n+2)+j] -= val
        imos[(j+1)*(n+2)+r] += val
        # imos[l+1][j] += val
        # imos[l+1][r] -= val
        # imos[j+1][j] -= val
        # imos[j+1][r] += val
        right[l] = r
        left[r] = l

for i in range(n+1):
    for j in range(1,n+1):
        imos[i*(n+2)+j] += imos[i*(n+2)+j-1]
        # imos[i][j] += imos[i][j-1]

for i in range(1,n+1):
    for j in range(n+1):
        imos[i*(n+2)+j] += imos[(i-1)*(n+2)+j]
        # imos[i][j] += imos[i-1][j]

ans = 0
for i in range(1,n+1):
    dif = 0
    for j in range(i,n+1):
        ans = max(ans,imos[i*(n+2)+j] - dif)
        dif += a[j-1]

print(ans)

Submission status: Runtime Error

Solution code:
a, b = map(str, input(), split())
if a.lower() == b:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# input
deck = input()
SHDC = [[0] * 5 for _ in range(4)]  # それぞれのマークの10~12が出たかを管理
pos = 0
Mark = "SHDC"
Flash = ["10", "J", "Q", "K", "A"]
remove_mark = ""
while True:
    if deck[pos + 1] in Flash or 50 <= ord(deck[pos + 1]) <= 57:
        mark = deck[pos]
        num = deck[pos + 1]
        pos += 2
    elif deck[pos + 2] in Mark:
        mark = deck[pos]
        num = deck[pos + 1]
        pos += 2
    else:
        mark = deck[pos]
        num = deck[pos + 1 : pos + 3]
        pos += 3
    if num in Flash:
        SHDC[Mark.index(mark)][Flash.index(num)] = 1
        if sum(SHDC[Mark.index(mark)]) == 5:
            remove_mark = mark
            break

ans = ""
cnt = 0
while True:
    if deck[pos + 1] in Flash or 50 <= ord(deck[pos + 1]) <= 57:
        mark = deck[pos]
        num = deck[pos + 1]
        pos += 2
    elif deck[pos + 2] in Mark:
        mark = deck[pos]
        num = deck[pos + 1]
        pos += 2
    else:
        mark = deck[pos]
        num = deck[pos + 1 : pos + 3]
        pos += 3
    if mark == remove_mark and num in Flash:
        ans += mark + num
    else:
        cnt += 1
        if cnt == 5:
            break
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# input
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, a, b = map(int, input().split())
x = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
    ans += min(b, a * (x[i + 1] - x[i]))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*(N+1)
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (not filled[i-1]) else left[i-1]
        r = i if (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
	        if i<N-1:
                ticket_sum[(i+1)*N+r+1]+=x

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)