Python代码

a,b,c,m=map(int,input().split())
nums=list(map(int,input().split()))
attack=[[0]]
N=(a+1)*(b+1)*(c+1)+1
diff1=[0 for _ in range(N)]
boat=[0 for _ in range(N)]
def get(i,j,k):
    global a,b,c
    return i*b*c+j*c+k
def insert(x1,y1,z1,x2,y2,z2,c,diff):#差分数组更新
    diff[get(x1,y1,z1)]+=c
    diff[get(x1,y1,z2+1)]-=c
    diff[get(x2+1,y2+1,z2+1)]-=c
    diff[get(x1,y2+1,z1)]-=c
    diff[get(x1,y2+1,z2+1)]+=c
    diff[get(x2+1,y1,z1)]-=c
    diff[get(x2+1,y1,z2+1)]+=c
    diff[get(x2+1,y2+1,z1)]+=c
t=0
for i in range(1,a+1):
    for j in range(1,b+1):
        for k in range(1,c+1):
            boat[get(i,j,k)]=nums[t]
            t+=1
for i in range(1,a+1):#初始化差分数组
    for j in range(1,b+1):
        for k in range(1,c+1):
            insert(i,j,k,i,j,k,boat[get(i,j,k)],diff1)
for _ in range(m):#攻击回合
        attack.append(list(map(int,input().split())))
def check(x):
    global a,b,c
    diff_copy=diff1[:]#深复制初始数组
    boat_copy=[0 for _ in range(N)]
    for i in range(1,x+1):#更新差分数组
        la,ra,lb,rb,lc,rc,h=attack[i]
        insert(la,lb,lc,ra,rb,rc,-h,diff_copy)
    for i in range(1,a+1):#对差分数组求三位前缀和即战舰更新后的生命值
        for j in range(1,b+1):
            for k in range(1,c+1):
                boat_copy[get(i,j,k)]=diff_copy[get(i,j,k)]+boat_copy[get(i-1,j,k)]+\
                boat_copy[get(i,j-1,k)]+boat_copy[get(i,j,k-1)]+\
                boat_copy[get(i-1,j-1,k-1)]-boat_copy[get(i-1,j-1,k)]-\
                boat_copy[get(i-1,j,k-1)]-boat_copy[get(i,j-1,k-1)]
                if boat_copy[get(i,j,k)]<0:
                    return True

    return False

left,right=1,m
while left+1<right:#二分答案
    mid=(left+right)//2
    if check(mid):
        right=mid
    else:
        left=mid
if check(left):
    print(left)
else:
    print(right)