結果

問題 No.655 E869120 and Good Triangles
ユーザー gew1fw
提出日時 2025-06-12 14:27:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,491 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 456,832 KB
最終ジャッジ日時 2025-06-12 14:27:45
合計ジャッジ時間 4,874 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 10 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, K, P = map(int, sys.stdin.readline().split())
    black = []
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        black.append((x-1, y-1))  # 0-based index

    # Initialize a[i][j]
    a = [[float('inf')] * (N+1) for _ in range(N+1)]
    for x, y in black:
        a[x][y] = 0

    # Multi-source BFS
    q = deque()
    for x, y in black:
        q.append((x, y))
    dirs = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, 1), (0, -1)]
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny <= nx:
                if a[nx][ny] > a[x][y] + 1:
                    a[nx][ny] = a[x][y] + 1
                    q.append((nx, ny))

    # Compute row-wise prefix sums
    row_sum = [[0]*(N+2) for _ in range(N+2)]
    for i in range(N):
        current = 0
        for j in range(i+1):
            current += a[i][j]
            row_sum[i][j] = current

    # For each (i,j), precompute the sum for each possible s
    # and find the minimal s where sum >= P
    answer = 0

    for i in range(N):
        for j in range(i+1):
            s_max = N - i
            if s_max == 0:
                continue
            # Precompute the sum for s=1 to s_max
            # sum_s[s] is the sum for size s
            sum_s = [0] * (s_max + 1)
            for s in range(1, s_max + 1):
                total = 0
                for a_step in range(s):
                    k = i + a_step
                    l_start = j
                    l_end = j + a_step
                    if l_end > k:
                        l_end = k
                    sum_row = row_sum[k][l_end] - (row_sum[k][l_start - 1] if l_start > 0 else 0)
                    total += sum_row
                sum_s[s] = total
                if sum_s[s] >= P:
                    break  # No need to compute further for this s

            # Find the minimal s where sum_s[s] >= P
            # Since sum_s is non-decreasing, we can break early
            found = False
            min_s = None
            for s in range(1, s_max + 1):
                if sum_s[s] >= P:
                    min_s = s
                    found = True
                    break
            if found:
                count = s_max - min_s + 1
                answer += count

    print(answer)

if __name__ == "__main__":
    main()
0