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: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

# 二分探索木の代わり BST HST
# 存在しない要素に対するremoveはこないことを仮定している

from heapq import heappop as hpp, heappush as hp
class HST:
    def __init__(self, ascending=True):
        self._h = []
        self._q = []
        self.ascending = ascending
    def push(self, v):
        if not self.ascending:
            v *= -1
        hp(self._h, v)
    def remove(self, v):
        if not self.ascending:
            v *= -1
        hp(self._q, v)
    def top(self):
        while self._q and self._q[0]==self._h[0]:
            hpp(self._q)
            hpp(self._h)
        if not self._h:
            res = None
        else:
            res = self._h[0]
            if not self.ascending:
                res *= -1
        return res

# inputna
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for _ in range(n)]
ans = 0
hs = [HST(ascending=False) for _ in range(m)]
j = 0
val = 0
prv = 0
def sub():
    return sum(hs[i].top() for i in range(m))
for i in range(n):
    if i>=1:
        val += a[i-1]
    for k in range(m):
        hs[k].push(b[i][k])
ans = sub() - val
l = 0
r = n-1
for _ in range(n-1):
    for k in range(m):
        hs[k].remove(b[l][k])
    val -= a[l]
    v1 = sub() - val
    
    for k in range(m):
        hs[k].push(b[l][k])
    val += a[l]
    
    val -= a[r-1]
    for k in range(m):
        hs[k].remove(b[r][k])
    v2 = sub() - val
    if v1>v2:
        for k in range(m):
            hs[k].push(b[r][k])
        val += a[r-1]

        val -= a[l]
        for k in range(m):
            hs[k].remove(b[l][k])
        l += 1
    else:
        r -= 1
    ans = max(ans, v1, v2)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.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,i.split())) for i in  readlines()]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)
print('hoge')

# maspyさん提出のコピペでメモリ利用量をチェックしたいだけ

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.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()))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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.9):
            print(ans)
            exit()

    print(ans)

if __name__ == '__main__':
    main()

'''
嘘解答です
'''

Submission status: Wrong Answer

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 = [[] for _ in range(n+2)]
for i in range(n+2):
    imos[i] = [0] * (n+3-i)

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-l] += val
        imos[l+1][r-l] -= val
        imos[j+1][j-j] -= val
        imos[j+1][r-j] += val
        right[l] = r
        left[r] = l

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

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

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

print(ans)

Submission status: Wrong Answer

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

print(9)    
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: Wrong Answer

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-1]))

print(ans)

Submission status: Wrong Answer

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)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(1,N))+[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

# 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: Wrong Answer

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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import numpy as np

N,M = map(int,readline().split())
A = np.array(readline().split(),np.int64)
B = np.array(read().split(),np.int64).reshape(N,M)

"""
・各B_ij の影響範囲を調べる。あるL,Rに対して、[L,x] x [x,R] の形で採用される
・この形は長方形なので、imos更新できる
"""

# 番兵となるお店を追加する
INF = 10**9 + 100
B = np.pad(B,((1,1),(0,0)),'constant',constant_values=INF)

filled = np.zeros((N+2,M),dtype=np.bool)
left = np.tile(np.arange(N+2)[:,None],(1,M))
right = np.tile(np.arange(N+2)[:,None],(1,M))
L = np.zeros((N+2,M),dtype=np.int32)
R = np.zeros((N+2,M),dtype=np.int32)

ind = B.argsort(axis=0)
I = np.arange(M)
for x in ind[:-2]:
    # x番目に要素を追加。その時点での連結成分の左端、右端を書き込む
    filled[x,I] = True
    l = np.where(filled[x-1,I],left[x-1,I],x)
    r = np.where(filled[x+1,I],right[x+1,I],x)
    right[l] = r; left[r] = l; L[x,I] = l; R[x,I] = r

Submission status: Wrong Answer

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

import numpy as np

N,M = map(int,readline().split())
A = np.array(readline().split(),np.int64)
B = np.array(read().split(),np.int64).reshape(N,M)

"""
・各B_ij の影響範囲を調べる。あるL,Rに対して、[L,x] x [x,R] の形で採用される
・この形は長方形なので、imos更新できる
"""

# 番兵となるお店を追加する
INF = 10**9 + 100
B = np.pad(B,((1,1),(0,0)),'constant',constant_values=INF)

filled = np.zeros((N+2,M),dtype=np.bool)
left = np.tile(np.arange(N+2)[:,None],(1,M))
right = np.tile(np.arange(N+2)[:,None],(1,M))
L = np.zeros((N+2,M),dtype=np.int32)
R = np.zeros((N+2,M),dtype=np.int32)

ind = B.argsort(axis=0)
I = np.arange(M)
for x in ind[:-2]:
    # x番目に要素を追加。その時点での連結成分の左端、右端を書き込む
    filled[x,I] = True
    l = np.where(filled[x-1,I],left[x-1,I],x)
    r = np.where(filled[x+1,I],right[x+1,I],x)
    right[l] = r; left[r] = l; L[x,I] = l; R[x,I] = r

opt_ticket = np.zeros((N+2,N+2),dtype=np.int64)

for x in range(1,N+1):
    l = L[x]; b = B[x]; r = R[x]
    np.add.at(opt_ticket,(l,x),b)
    np.add.at(opt_ticket,(x+1,x),-b.sum())
    np.add.at(opt_ticket,(l,r+1),-b)
    np.add.at(opt_ticket,(x+1,r+1),b)

np.cumsum(opt_ticket,axis=0,out=opt_ticket)
np.cumsum(opt_ticket,axis=1,out=opt_ticket)

X = np.cumsum(np.concatenate([[0],A]))
dist_mat = np.triu(X[None,:] - X[:,None])

happy = opt_ticket[1:-1,1:-1] - dist_mat
answer = happy.max()
print(answer)

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().strip().split(" "))
a = map(int, raw_input().strip().split(" "))
b = [None] * n
for i in range(n):
	b[i] = map(int, raw_input().strip().split())
result = reduce(lambda x, y: x + y, b[0])
t = result
max_b = b[0]
for i in range(1, n):
	cost = a[i - 1]
	benefit = 0
	for j in range(m):
		if max_b[j] < b[i][j]:
			benefit += b[i][j] - max_b[j]
			max_b[j] = b[i][j]
	t += benefit - cost
	if t > result:
		result = t
print result

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

    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: Time 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)]

    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: 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,njit,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
def solve_imos(imos):
    res = np.cumsum(imos, axis=1)
    res = np.cumsum(res, axis=0)
    return res


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]

    imos = solve_imos(imos)

    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:
def main():
    from sys import stdin
    read = stdin.buffer.read
    readline = stdin.buffer.readline
    from collections import defaultdict
    from itertools import accumulate

    n,m = map(int,readline().split())
    a = tuple(map(int,readline().split()))
    b = tuple(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+3-i)
        for j,val in query[i].items():
            next[j+1-i] += val

        for j,val in enumerate(accumulate(next),i-1):
            imos[j] += val
        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
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+3-i)
        for j,val in query[i].items():
            next[j+1-i] += val

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    read = stdin.buffer.read
    readline = stdin.buffer.readline
    from collections import defaultdict
    from itertools import accumulate
    
    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)]
    l0 = list(range(-1,n+1))
    r0 = list(range(1,n+3))

    for i in range(m):
        left = l0[::]
        right = r0[::]

        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

    next0 = [0] * (n+2)
    imos = next0[::]
    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 = next0[:(n+3-i)]
        for j,val in query[i].items():
            next[j+1-i] += val

        for j,val in enumerate(accumulate(next),i-1):
            imos[j] += val
        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
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)]
    l0 = list(range(-1,n+1))
    r0 = list(range(1,n+3))

    for i in range(m):
        left = l0[::]
        right = r0[::]

        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

    next0 = [0] * (n+2)
    imos = next0[::]
    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 = next0[:(n+3-i)]
        for j,val in query[i].items():
            next[j+1-i] += val

        for j,val in enumerate(accumulate(next),i-1):
            imos[j] += val
        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
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+3-i)
        for j,val in query[i].items():
            next[j+1-i] += val

        for j,val in enumerate(accumulate(next),i-1):
            imos[j] += val
        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
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+3-i)
        for j,val in query[i].items():
            next[j+1-i] += val

        next = list(accumulate(next))

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

    print(ans)

if __name__ == '__main__':
    main()