結果

問題 No.755 Zero-Sum Rectangle
コンテスト
ユーザー titia
提出日時 2025-02-10 03:20:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 964 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 77,288 KB
最終ジャッジ日時 2025-02-10 03:21:07
合計ジャッジ時間 16,502 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
A=[list(map(int,input().split())) for i in range(m)]

S=[[0]*(m+2) for i in range(m+2)]

for i in range(m):
    for j in range(m):
        S[i][j]=S[i-1][j]+A[i][j]

for i in range(m):
    for j in range(1,m):
        S[i][j]=S[i][j-1]+S[i][j]

def rectsum(x,y,z,w):
    return S[z][w]-S[z][y-1]-S[x-1][w]+S[x-1][y-1]

LS=[[0]*(m+2) for i in range(m+2)]

for i in range(m):
    for j in range(i,m):
        for k in range(m):
            for l in range(k,m):
                xx=rectsum(i,k,j,l)

                if xx==0:
                    LS[i][k]+=1
                    LS[i][l+1]-=1
                    LS[j+1][k]-=1
                    LS[j+1][l+1]+=1

for i in range(1,m+2):
    for j in range(m+2):
        LS[i][j]+=LS[i-1][j]

for i in range(m+2):
    for j in range(1,m+2):
        LS[i][j]+=LS[i][j-1]

for i in range(n):
    x,y=map(int,input().split())
    print(LS[x-1][y-1])
0