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: Time Limit Exceeded

Solution code:
from sys import stdin
read = stdin.buffer.read
readline = stdin.buffer.readline
from collections import defaultdict
from itertools import accumulate

def main():
    n,m = map(int,readline().split())
    a = list(map(int,readline().split()))
    b = list(map(int,read().split()))

    query = [defaultdict(int) 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]
            query[l+1][j] += val
            query[l+1][r] -= val
            query[j+1][j] -= val
            query[j+1][r] += val
            right[l] = r
            left[r] = l

    imos = [0] * (n+2)
    for i,ai in enumerate(a,2):
        imos[i] = imos[i-1] - ai
        query[i][i] += ai

    ans = 0
    for i in range(1,n+1):
        next = [0] * (n+2)
        for j,val in query[i].items():
            next[j] += val

        next = list(accumulate(next))

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict
import time

def main():
    s = time.time()

    n,m = map(int,readline().split())
    a = list(map(int,readline().split()))
    b = list(map(int,read().split()))

    query = [defaultdict(int) 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]
            query[l+1][j] += val
            query[l+1][r] -= val
            query[j+1][j] -= val
            query[j+1][r] += val
            right[l] = r
            left[r] = l

    imos = [0] * (n+2)
    for i,ai in enumerate(a,2):
        imos[i] = imos[i-1] - ai
        query[i][i] += ai

    ans = 0
    for i in range(1,n+1):
        next = [0] * (n+2)
        for j,val in query[i].items():
            next[j] += val

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

        if(time.time() - s > 1.95):
            print(ans)
            exit()

    print(ans)

if __name__ == '__main__':
    main()

'''
嘘解答です
'''

Submission status: Time Limit Exceeded

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

def main():
    n,m = map(int,readline().split())
    a = tuple(map(int,readline().split()))
    b = tuple(map(int,read().split()))

    query = [[] 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]
            query[l+1].append((j,r,val))
            query[j+1].append((j,r,val*-1))
            right[l] = r
            left[r] = l

    imos = [0] * (n+2)
    for i,ai in enumerate(a,2):
        imos[i] = imos[i-1] - ai

    ans = 0
    for i in range(1,n+1):
        next = [0] * (n+2)
        if(i>=2):
            next[i] += a[i-2]
        for l,r,val in query[i]:
            next[l] += val
            next[r] -= val

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n,m = map(int,readline().split())
    a = tuple(map(int,readline().split()))
    b = tuple(map(int,read().split()))

    query = []
    for i in range(n+2):
        query.append(dict())

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

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

            if(r in query[l+1]):
                query[l+1][r] -= val
            else:
                query[l+1][r] = val*-1

            if(j in query[j+1]):
                query[j+1][j] -= val
            else:
                query[j+1][j] = val*-1

            if(r in query[j+1]):
                query[j+1][r] += val
            else:
                query[j+1][r] = val
            right[l] = r
            left[r] = l

    imos = [0] * (n+2)
    for i,ai in enumerate(a,2):
        imos[i] = imos[i-1] - ai
        query[i][i] += ai

    ans = 0
    for i in range(1,n+1):
        next = [0] * (n+2)
        for j,val in query[i].items():
            next[j] += val

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n,m = map(int,readline().split())
    a = list(map(int,readline().split()))
    b = list(map(int,read().split()))

    query = [defaultdict(int) 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]
            query[l+1][j] += val
            query[l+1][r] -= val
            query[j+1][j] -= val
            query[j+1][r] += val
            right[l] = r
            left[r] = l

    imos = [0] * (n+2)
    for i,ai in enumerate(a,2):
        imos[i] = imos[i-1] - ai
        query[i][i] += ai

    ans = 0
    for i in range(1,n+1):
        next = [0] * (n+2)
        for j,val in query[i].items():
            next[j] += val

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time 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]
a = tuple(a)
b = tuple(map(int,read().split()))

ans = 0
imos = [[0] * (n+2) for _ in range(2)]
query = [dict() for _ in range(n+2)]
for i in range(n-1):
    imos[0][i+2] -= a[i]
    if(i+2 in query[i+2]):
        query[i+2][i+2] += a[i]
    else:
        query[i+2][i+2] = a[i]
for i in range(n+1):
    imos[0][i+1] += imos[0][i]

bi = [0] * n

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

    for j,val in enumerate(b[i::m], 1):
        bi[j-1] = (val,j)
    bi.sort()

    for val,j in bi:
        l = left[j]
        r = right[j]
        for x,y,val2 in zip([l+1,l+1,j+1,j+1],[j,r,j,r],[val,-val,-val,val]):
            if(y in query[x]):
                query[x][y] += val2
            else:
                query[x][y] = val2
        right[l] = r
        left[r] = l

for i in range(1,n+1):
    i0 = 1-(i%2)
    i1 = i%2
    for j in range(0,n+1):
        imos[i1][j] = 0
    for qi,val in query[i].items():
        imos[i1][qi] += val
    for j in range(i,n+1):
        imos[i1][j] += imos[i1][j-1]
    for j in range(i,n+1):
        imos[i1][j] += imos[i0][j]
        ans = max(ans,imos[i1][j])

print(ans)

Submission status: Time 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()))

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

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

    for j,val in enumerate(b[i::m], 1):
        bi[j-1] = (val,j)
    bi.sort()

    for val,j in bi:
        l = left[j]
        r = right[j]
        query[l+1].append((j,val))
        query[l+1].append((r,-1*val))
        query[j+1].append((j,-1*val))
        query[j+1].append((r,val))
        right[l] = r
        left[r] = l

for i in range(1,n+1):
    i0 = 1-(i%2)
    i1 = i%2
    for j in range(max(0,i-1),n+2):
        imos[i1][j] = 0
    for qi,val in query[i]:
        imos[i1][qi] += val
    for j in range(i,n+1):
        imos[i1][j] += imos[i1][j-1]
    dif = 0
    for j in range(i,n+1):
        imos[i1][j] += imos[i0][j]
        ans = max(ans,imos[i1][j] - dif)
        dif += a[j-1]

print(ans)

Submission status: Time 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()))

ans = 0
imos = [[0] * (n+2) for _ in range(2)]
query = [[] 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]
        query[l+1].append((j,val))
        query[l+1].append((r,-1*val))
        query[j+1].append((j,-1*val))
        query[j+1].append((r,val))
        right[l] = r
        left[r] = l

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

print(ans)

Submission status: Time 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 = [[False] * (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(i,n+1):
        imos[i][j] += imos[i][j-1]

for i in range(1,n+1):
    for j in range(i,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: Time Limit Exceeded

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()))

# import random
# n = 5000
# m = 200
# a = [random.randint(5*10**8,10**9) for _ in range(n-1)]
# a += [0,0,0]
# b = [random.randint(5*10**8,10**9) for _ in range(n*m)]

imos = array('q')
for _ in range((n+2)**2):
    imos.append(0)

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]
        li = (l+1)*(n+2)
        ji = (j+1)*(n+2)
        imos[li+j] += val
        imos[li+r] -= val
        imos[ji+j] -= val
        imos[ji+r] += val
        right[l] = r
        left[r] = l

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

for i in range(1,n+1):
    ii = i*(n+2)
    ii2 = (i-1)*(n+2)
    for j in range(n+1):
        imos[ii+j] += imos[ii2+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: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from numba import jit,prange
import numpy as np

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
a += [0,0,0]
b = list(map(int,read().split()))
imos = np.zeros((n+2,n+2),dtype=('int'))

@jit(nopython=True, parallel=True)
def solve(n,m,a,b,imos):
    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 prange(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 prange(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(int(ans))

solve(n,m,a,b,imos)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from numba import jit
import numpy as np

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

@jit
def solve(n,m,a,b):
    # imos = [[0] * (n+2) for _ in range(n+2)]
    imos = np.zeros((n+2,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(int(ans))

solve(n,m,a,b)

Submission status: Time Limit Exceeded

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

class Sparsetable:
    def __init__(self, B):
        self.B = B
        self.N = len(B)
        A = list(range(self.N))
        self.bn = self.N.bit_length()
        self.res = [[None]*self.bn for _ in range(self.N)]
        for i in range(self.N):
            self.res[i][0] = A[i]
        
        for dn in range(1, self.bn):
            rn = 1<<(dn-1)
            for h in range(self.N-2*rn+1):
                self.res[h][dn] = self.spf(self.res[h][dn-1], self.res[h+rn][dn-1])
    
    def spf(self, x, y):
        if self.B[x] > self.B[y]:
            return x
        return y
    
    def query(self, h1, h2):
        h2 -= 1
        hl = h2-h1+1
        bh = hl.bit_length()-1
        rh = 1<<bh
        return self.spf(self.res[h1][bh], self.res[h2-rh+1][bh])
    

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

B = [list(map(int, readline().split())) for _ in range(N)]
B = list(map(list, zip(*B)))

table = [[0]*(N+1) for _ in range(N+1)]

for j in range(M):
    St = Sparsetable(B[j])
    stack = [(0, N)]
    
    while stack:
        l, r = stack.pop()
        
        am = St.query(l, r)
        b = B[j][am]
        table[l][r-1] += b
        table[l][am-1] -= b
        table[am+1][r-1] -= b
        table[am+1][am-1] += b
        if am != l:
            stack.append((l, am))
        if am+1 != r:
            stack.append((am+1, r))
    
for r in range(N-1, -1, -1):
    for l in range(1, r+1):
        table[l][r] += table[l-1][r]
for r in range(N-2, -1, -1):
    for l in range(r+1):
        table[l][r] += table[l][r+1]

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
        ans = max(ans, table[i][j-1] - (A[j-1] - A[i]))

print(ans)

Submission status: Time Limit Exceeded

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

class Sparsetable:
    def __init__(self, B):
        self.B = B
        self.N = len(B)
        A = list(range(self.N))
        self.bn = self.N.bit_length()
        self.res = [[None]*self.bn for _ in range(self.N)]
        for i in range(self.N):
            self.res[i][0] = A[i]
        
        for dn in range(1, self.bn):
            rn = 1<<(dn-1)
            for h in range(self.N-2*rn+1):
                self.res[h][dn] = self.spf(self.res[h][dn-1], self.res[h+rn][dn-1])
    
    def spf(self, x, y):
        if self.B[x] > self.B[y]:
            return x
        return y
    
    def query(self, h1, h2):
        h2 -= 1
        hl = h2-h1+1
        bh = hl.bit_length()-1
        rh = 1<<bh
        return self.spf(self.res[h1][bh], self.res[h2-rh+1][bh])
    

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

B = [list(map(int, readline().split())) for _ in range(N)]
B = list(map(list, zip(*B)))

table = [[0]*(N+1) for _ in range(N+1)]

for j in range(M):
    St = Sparsetable(B[j])
    stack = [(0, N)]
    
    while stack:
        l, r = stack.pop()
        
        am = St.query(l, r)
        b = B[j][am]
        table[l][am] += b
        table[l][r] -= b
        table[am+1][am] -= b
        table[am+1][r] += b
        if am != l:
            stack.append((l, am))
        if am+1 != r:
            stack.append((am+1, r))
    
for i in range(1, N+1):
    for j in range(N+1):
        table[i][j] += table[i-1][j]
for j in range(1, N+1):
    for i in range(N+1):
        table[i][j] += table[i][j-1]

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
        ans = max(ans, table[i][j-1] - (A[j-1] - A[i]))

print(ans)

Submission status: Time 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]

I = []
X = []
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]
        I.append(l*N+i); X.append(x)
        if i<N-1:
            I.append((i+1)*N+i); X.append(-x)
        if r<N-1:
            I.append(l*N+r+1); X.append(-x)
        if i<N-1 and r<N-1:
            I.append((i+1)*N+r+1); X.append(x)

del B

ticket_sum = [0]*(N*N)
for i,x in zip(I,X):
    ticket_sum[i] += 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)

Submission status: Time 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 = tuple(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: Time 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 = [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)

for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(1,N))+[0,0]
    right = list(range(-1,N))
    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: Time 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 = [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=lambda i: arr[i]):
        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 and r<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)

Submission status: Time 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 = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

N,M

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

add_list = []

# 各区間 [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]
        add_list.append((l*N+i,x))
        if i<N-1:
            add_list.append(((i+1)*N+i,-x))
        if r<N-1:
            add_list.append((l*N+r+1,-x))
        if i<N-1 and r<N-1:
            add_list.append(((i+1)*N+r+1,x))

del B

ticket_sum = [0]*(N*N)
for i,x in add_list:
    ticket_sum[i] += 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)

Submission status: Time 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 = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

N,M

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 and r<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)

Submission status: Time 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 = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

N,M

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
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (i==0) or (not filled[i-1]) else left[i-1]
        r = i if (i==N-1) or (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 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

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

dist = [0]*(N*N)
for i in range(N):
    for j in range(i,N):
        dist[i*N+j] = A[j]-A[i]

answer = max(x-y for x,y in zip(ticket_sum,dist))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,m = LI()
    a = LI()
    b = [LI() for _ in range(n)]
    rr = 0
    for si in range(n):
        mb = b[si]
        r = sum(mb)
        k = 0
        if r > rr:
            rr = r
        for i in range(si+1,n):
            tb = b[i]
            k += a[i-1]
            for j in range(m):
                if mb[j] < tb[j]:
                    mb[j] = tb[j]

            t = sum(mb) - k

            if rr < t:
                rr = t

    return rr


print(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,i.split())) for i in  readlines()]

    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[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()