Submission #6902831

---

Source Code Expand

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    def comb(a,b):
        if b > a:
            return 0
        return fact[a]*inv[b]*inv[a-b]%mod
    def f(x,y):
        return comb(x*y,k)
    w,h = LI()
    x,y = LI()
    d,l = LI()
    fact = [1]
    for i in range(10000):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*10001
    inv[10000] = pow(fact[10000],mod-2,mod)
    for i in range(10000)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    k = d+l
    ans = f(x,y)-2*f(x-1,y)-2*f(x,y-1)+f(x-2,y)+f(x,y-2)+4*f(x-1,y-1)-2*f(x-2,y-1)-2*f(x-1,y-2)+f(x-2,y-2)
    ans %= mod
    ans *= (w-x+1)*(h-y+1)
    ans *= comb(k,d)
    ans %= mod
    print(ans)
    return

#B
def B():
    n = I()
    d = LIR(n)
    for i in range(n):
        for j in range(n-1):
            d[i][j+1] += d[i][j]
    for j in range(n):
        for i in range(n-1):
            d[i+1][j] += d[i][j]
    for i in range(n):
        d[i].insert(0,0)
    d.insert(0,[0]*(n+1))
    f = [0]*(n**2+1)
    for l in range(n):
        for u in range(n):
            for r in range(l+1,n+1):
                w = r-l
                for d_ in range(u+1,n+1):
                    h = d_-u
                    f[w*h] = max(f[w*h],d[r][d_]-d[r][u]-d[l][d_]+d[l][u])
    q = I()
    for i in range(n**2):
        f[i+1] = max(f[i+1],f[i])
    for i in range(q):
        x = I()
        print(f[x])
    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#Solve
if __name__ == "__main__":
    B()

Submission Info

Judge Result