結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, K, P = map(int, sys.stdin.readline().split())
    black = set()
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        black.add((x, y))
    
    # Initialize a array
    a = [[float('inf')] * (N + 2) for _ in range(N + 2)]  # 1-based indexing
    q = deque()
    for (x, y) in black:
        a[x][y] = 0
        q.append((x, y))
    
    # Directions: up, down, left, right (but considering the grid structure)
    # Wait, the grid is such that each point (i, j) has up to three neighbors:
    # (i-1, j), (i-1, j-1), (i, j+1) ?
    # Or, perhaps better to define all possible directions
    # For example, each (i,j) can go to (i+1,j), (i,j+1), (i+1, j+1) ?
    # Or perhaps the grid is such that each point (i,j) has neighbors (i+1,j), (i,j+1), (i+1, j+1).
    # But this may vary. Alternatively, perhaps the grid is such that each point (i,j) has neighbors:
    # (i-1, j-1), (i-1, j), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1)
    # But this seems too many. Alternatively, perhaps the grid is such that each point (i,j) is connected to:
    # (i+1,j), (i, j+1), (i+1, j+1)
    # Or perhaps it's a hexagonal grid. This may complicate the problem.
    # Given the problem statement, perhaps the grid is a triangular grid where each point (i,j) has neighbors:
    # (i-1, j-1), (i-1, j), (i, j-1), etc.
    # However, given the lack of clarity, perhaps it's better to represent the grid as a graph where each point (i,j) can move to adjacent points as per the grid's structure.
    # Alternatively, perhaps the grid is such that each point (i,j) has up to six neighbors, but this may be too complex.
    # Given the problem statement, perhaps the distance is calculated in such a way that each step moves to an adjacent point in the grid, which is a triangular grid.
    # However, to avoid confusion, perhaps the problem assumes that each point (i,j) has neighbors (i+1,j), (i,j+1), (i+1, j+1).
    # Or perhaps the problem considers that each point has neighbors to the right and below, but this is unclear.
    # Given that, perhaps we can model the grid as follows:
    # Each point (i,j) can move to (i+1, j), (i, j+1), and (i+1, j+1).
    # However, this may not capture all possible neighbors. Alternatively, perhaps it's better to model the grid with all possible neighbors.
    # Given the uncertainty, perhaps we can proceed under the assumption that each point (i,j) can move to (i+1,j), (i-1,j), (i,j+1), (i,j-1), (i+1,j+1), (i-1,j-1), etc., but this is time-consuming.
    # Given the time constraints, perhaps it's better to assume that the grid is such that each point (i,j) can move to (i+1,j), (i-1,j), (i,j+1), (i,j-1), (i+1,j+1), (i-1,j-1), but this may not be correct.
    # Alternatively, perhaps the grid is such that each point (i,j) has neighbors (i-1,j-1), (i-1,j), (i,j-1), (i,j+1), (i+1,j-1), (i+1,j), (i+1,j+1). This may be too complex.
    # Given the problem statement's example, perhaps the grid is such that each point (i,j) can move to (i+1,j), (i,j+1), (i+1, j+1).
    # Therefore, the BFS will consider these three directions.
    directions = [ (1,0), (0,1), (1,1) ]
    
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 1 <= nx <= N and 1 <= ny <= nx and a[nx][ny] > a[x][y] + 1:
                a[nx][ny] = a[x][y] + 1
                q.append( (nx, ny) )
        for dx, dy in [ (-1,0), (0,-1), (-1,-1) ]:
            nx = x + dx
            ny = y + dy
            if 1 <= nx <= N and 1 <= ny <= nx and a[nx][ny] > a[x][y] + 1:
                a[nx][ny] = a[x][y] + 1
                q.append( (nx, ny) )
    
    # Preprocess row-wise prefix sums
    row_sum = [ [0]*(N+2) for _ in range(N+2) ]
    for x in range(1, N+1):
        for y in range(1, x+1):
            row_sum[x][y] = row_sum[x][y-1] + a[x][y]
    
    result = 0
    
    for i in range(1, N+1):
        for j in range(1, i+1):
            s_max = N - i + 1
            current_sum = 0
            for s in range(1, s_max + 1):
                x = i + s - 1
                if x > N:
                    break
                y_start = j
                y_end = j + s - 1
                if y_end > x:
                    y_end = x
                if y_start > y_end:
                    sum_layer = 0
                else:
                    sum_layer = row_sum[x][y_end] - row_sum[x][y_start - 1]
                current_sum += sum_layer
                if current_sum >= P:
                    result += 1
    
    print(result)

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