結果

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

ソースコード

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(n):
    for j in range(m):
        S[i][j]=S[i-1][j]+A[i][j]

for i in range(n):
    for j in range(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