結果

問題 No.755 Zero-Sum Rectangle
コンテスト
ユーザー raven7959
提出日時 2021-10-18 23:29:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,273 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 212 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 77,256 KB
最終ジャッジ日時 2024-09-19 20:17:56
合計ジャッジ時間 18,686 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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