本题的目标是从一个包含正数和负数的三角形数组中找到一个元素和最小的子三角形。

比如在下例中，可以验证用红线标出的三角形满足题意，它的元素和是-42。

本题将考察一个一千行的三角形数组，其中的数由以下伪随机数算法（称为线性同余生成器）生成： \begin{align*} t_0&=0 \\ t_k&=(615949\times t_{k-1}+797807) \bmod 2^{20} \\ s_k&=t_k-2^{19} \\ \end{align*} 例如$s_1=273519$，$s_2=−153582$，$s_3=450905$，依此类推。所生成的数$s_k$的范围在$\pm 2^{19}$之间，共需生成500500个数，并将其按如下方式填入三角形数组： $$\begin{matrix} s_1 & & & \\ s_2 & s_3 & & \\ s_4 & s_5 & s_6 & \\ s_7 & s_8 & s_9 & s_{10} \\ \ldots & & & \\ \end{matrix}$$ 子三角形可以以任意元素为顶点（例如第i行第j列的元素)，每一行从顶点所在的列开始，并比上一行多一个数。求所有子三角形的元素和中最小的和数。

本题难度:

解答

令$S_{i,j}$为第i行第j列处的元素，并记$T_{i,j,d}$为以$S_{i,j}$为顶点且高度为d（即共d行）的三角形，那么这一三角形的元素为

在第$j$列：$S_{i,j}, S_{i+1,j},\ldots, S_{i+d-1,j}$，

在第$j+1$列：$S_{i+1,j+1}, S_{i+2,j+1},\ldots, S_{i+d-1,j+1}$，

。。。

在第$j+d-1$列：$S_{i+d-1,j+d-1}$。

若$T_{i,j,d}$是元素和最小的子三角形，则显然其从左侧数起前k列的和都必须为负数，否则$T_{i+k,j+k,d-k}$和将更小，这一结论对$k\in\{1,2,\ldots, d-1\}$都成立。

类似地，对该三角形最后k行的和也有同样的结论。

因此先分别按行和列计算三角形的前缀和，再遍历i、j、d（其中d从大到小遍历），找出符合上述标准的三角形，再从中取最小的和即可。缓存中间结果以避免重复计算。

最终答案是$-271248680$，它是$T_{7,7,886}$中元素的和（i、j从0开始计数）。

s,c,r,t,x,y=[],[],[],0,1 << 20,1 << 19
for i in range(1000):
    s.append([])
    c.append([])
    r.append([])
    for j in range(i+1):
        t=(615949*t+797807)%x
        s[-1].append(t-y)
        c[-1].append(c[i-1][j]+s[i][j] if i>0 and j< i else s[i][j])
        r[-1].append(r[-1][-1]+s[i][j] if j>0 else s[i][j])


print "start"

i,j,m,z=0,0,x,{}
while i < 1000:
    while j < i+1:
        d=1000-i
        u=c[i-1][j] if i>0 and j < i else 0
        v=r[i+d-1][j-1] if j>0 else 0
        q=[z[(x,y)] for x,y in z if i>=x and j>=y]
        while d>(max(q) if q else 0):
            a=c[i+d-1][j]-u
            b=r[i+d-1][j+d-1]-v
            k=1
            while k < d and a < 0 and b < 0:
                a+=(c[i+d-1][j+k]-c[i+k-1][j+k] if j < i else c[i+d-1][j+k])
                b+=(r[i+d-1-k][j+d-1-k]-r[i+d-1-k][j-1] if j>0 else r[i+d-1-k][j+d-1-k])
                k+=1
            if k==d:
                z[(i,j)]=d
                if a < m:
                    m=a
                    print i,j,d,m
                d=0
            else:
                d-=1
        j+=1
    i+=1

print m