結果

問題 No.655 E869120 and Good Triangles
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:31:26
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,362 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,484 KB
実行使用メモリ 611,064 KB
最終ジャッジ日時 2025-04-24 12:32:53
合計ジャッジ時間 4,833 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 10 MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, K, P = map(int, sys.stdin.readline().split())
    blacks = [tuple(map(int, sys.stdin.readline().split())) for _ in range(K)]

    # Initialize distance matrix with infinity
    INF = float('inf')
    a = [[INF] * (N + 2) for _ in range(N + 2)]  # 1-based indexing

    # Multi-source BFS setup
    q = deque()
    for x, y in blacks:
        a[x][y] = 0
        q.append((x, y))

    # Directions: six possible moves (dx, dy)
    directions = [(-1, -1), (-1, 0), (0, -1), (0, 1), (1, 0), (1, 1)]

    # Perform BFS to compute shortest distances
    while q:
        x, y = q.popleft()
        current_dist = a[x][y]
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 1 <= nx <= N and 1 <= ny <= nx:  # Check if within valid grid
                if a[nx][ny] > current_dist + 1:
                    a[nx][ny] = current_dist + 1
                    q.append((nx, ny))

    # Precompute prefix_row[i][j] = sum of a[i][1..j]
    prefix_row = [[0] * (N + 2) for _ in range(N + 2)]
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            prefix_row[i][j] = prefix_row[i][j - 1] + a[i][j]

    # Precompute diagonal_prefix_sum[i][j] for diagonal (i-j)
    diagonal_prefix_sum = [[0] * (N + 2) for _ in range(N + 2)]
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            if i - 1 >= j - 1 and j - 1 >= 1:
                diagonal_prefix_sum[i][j] = diagonal_prefix_sum[i - 1][j - 1] + prefix_row[i][j]
            else:
                diagonal_prefix_sum[i][j] = prefix_row[i][j]

    # Precompute column_prefix_sum[m][i] for column m up to row i
    column_prefix_sum = [[0] * (N + 2) for _ in range(N + 2)]
    for m in range(1, N + 1):
        for i in range(1, N + 1):
            if m > i:
                column_prefix_sum[m][i] = column_prefix_sum[m][i - 1]
            else:
                column_prefix_sum[m][i] = column_prefix_sum[m][i - 1] + prefix_row[i][m]

    answer = 0

    # Iterate over all possible starting points (i, j)
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            max_s = N - i + 1
            if max_s < 1:
                continue

            low = 1
            high = max_s
            ans = max_s + 1  # Initialize to invalid value

            while low <= high:
                mid = (low + high) // 2
                s = mid
                end_i = i + s - 1
                end_j = j + s - 1

                # Calculate sum1: sum of diagonal prefix sums
                if j - 1 >= 1 and i - 1 >= j - 1:
                    sum1 = diagonal_prefix_sum[end_i][end_j] - diagonal_prefix_sum[i - 1][j - 1]
                else:
                    sum1 = diagonal_prefix_sum[end_i][end_j]

                # Calculate sum2: sum of column prefix sums
                m = j - 1
                if m == 0:
                    sum2 = 0
                else:
                    sum2 = column_prefix_sum[m][end_i] - column_prefix_sum[m][i - 1]

                total = sum1 - sum2

                if total >= P:
                    ans = mid
                    high = mid - 1
                else:
                    low = mid + 1

            if ans <= max_s:
                answer += max_s - ans + 1

    print(answer)

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