AtCoder Beginner Contest 005

Submission #6902831

Source codeソースコード

#!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

Task問題 D - おいしいたこ焼きの焼き方
User nameユーザ名 tsumugi
Created time投稿日時
Language言語 PyPy3 (2.4.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 2230 Byte
File nameファイル名
Exec time実行時間 291 ms
Memory usageメモリ使用量 46192 KB

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 50 / 50 sub0.txt,sub1.txt,sub2.txt,sub_rand_max0.txt,sub_rand_max1.txt,sub_rand_max2.txt,sub_rand_max3.txt,sub_rand_min0.txt,s1.txt,s2.txt,sub0.txt,sub1.txt,sub2.txt,sub_rand_max0.txt,sub_rand_max1.txt,sub_rand_max2.txt,sub_rand_max3.txt,sub_rand_min0.txt
Subtask2 50 / 50 rand0.txt,rand1.txt,rand2.txt,rand3.txt,rand4.txt,rand_max0.txt,rand_max1.txt,rand_max2.txt,rand_max3.txt,rand_max4.txt,s1.txt,s2.txt,sub0.txt,sub1.txt,sub2.txt,sub_rand_max0.txt,sub_rand_max1.txt,sub_rand_max2.txt,sub_rand_max3.txt,sub_rand_min0.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
rand0.txt AC 279 ms 45552 KB
rand1.txt AC 230 ms 42992 KB
rand2.txt AC 266 ms 46192 KB
rand3.txt AC 210 ms 41456 KB
rand4.txt AC 195 ms 41200 KB
rand_max0.txt AC 288 ms 45936 KB
rand_max1.txt AC 286 ms 45936 KB
rand_max2.txt AC 291 ms 45936 KB
rand_max3.txt AC 281 ms 45808 KB
rand_max4.txt AC 291 ms 45936 KB
s1.txt AC 188 ms 39920 KB
s2.txt AC 185 ms 39920 KB
sub0.txt AC 189 ms 39920 KB
sub1.txt AC 182 ms 39920 KB
sub2.txt AC 181 ms 39920 KB
sub_rand_max0.txt AC 183 ms 39920 KB
sub_rand_max1.txt AC 176 ms 39920 KB
sub_rand_max2.txt AC 177 ms 39920 KB
sub_rand_max3.txt AC 176 ms 39920 KB
sub_rand_min0.txt AC 177 ms 39920 KB