結果

問題 No.755 Zero-Sum Rectangle
ユーザー raven7959raven7959
提出日時 2021-10-18 23:29:32
言語 PyPy3
(7.3.13)
結果
TLE  
実行時間 -
コード長 1,273 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 81,748 KB
実行使用メモリ 76,752 KB
最終ジャッジ日時 2023-10-20 00:25:25
合計ジャッジ時間 20,614 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
53,548 KB
testcase_01 TLE -
testcase_02 AC 1,737 ms
76,732 KB
testcase_03 AC 1,704 ms
76,724 KB
testcase_04 AC 1,688 ms
76,752 KB
testcase_05 AC 1,681 ms
76,520 KB
testcase_06 AC 1,653 ms
76,544 KB
testcase_07 AC 1,647 ms
76,384 KB
testcase_08 AC 1,645 ms
76,372 KB
testcase_09 AC 1,640 ms
76,344 KB
testcase_10 AC 1,640 ms
76,352 KB
testcase_11 AC 52 ms
64,296 KB
evil_1 AC 1,769 ms
77,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

def F_generate(h,w,a): #aは2次元配列
  da=[[0]*w for j in range(h)]
  da[0][0]=a[0][0]
  for i in range(1,w):
    da[0][i]=da[0][i-1]+a[0][i]
  for i in range(1,h):
    cnt_w=0
    for j in range(w):
      cnt_w+=a[i][j]
      da[i][j]=da[i-1][j]+cnt_w
  return da
def F_calc(F,p,q,x,y): #Fが2次元累積和の配列,左上のマスが(p,q),右下のマスが(x,y)の区間和
  if p>x or q>y:
    return 0
  if p==0 and q==0:
    return F[x][y]
  if p==0:
    return F[x][y]-F[x][q-1]
  if q==0:
    return F[x][y]-F[p-1][y]
  return F[x][y]-F[p-1][y]-F[x][q-1]+F[p-1][q-1]

N,M=map(int,input().split())
F=[list(map(int,input().split())) for _ in range(M)]
Q=[list(map(lambda x:int(x)-1,input().split())) for _ in range(N)]
da=F_generate(M,M,F)
ans=[[0]*(M+1) for _ in range(M+1)]
for x1 in range(M):
    for y1 in range(M):
        for x2 in range(x1,M):
            for y2 in range(y1,M):
                if F_calc(da,x1,y1,x2,y2)==0:
                    ans[x1][y1]+=1
                    ans[x1][y2+1]-=1
                    ans[x2+1][y1]-=1
                    ans[x2+1][y2+1]+=1
for i in range(M):
    for j in range(M):
        ans[i][j+1]+=ans[i][j]
for j in range(M):
    for i in range(M):
        ans[i+1][j]+=ans[i][j]
for x,y in Q:
    print(ans[x][y])
0