結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr += 1
    K = int(input[ptr]); ptr += 1
    P = int(input[ptr]); ptr += 1

    black = []
    for _ in range(K):
        x = int(input[ptr]); ptr += 1
        y = int(input[ptr]); ptr += 1
        black.append((x, y))
    
    # Initialize distance matrix
    INF = float('inf')
    dist = [ [INF] * (x + 1) for x in range(N + 1) ]  # dist[x][y] where y <= x <= N
    q = deque()
    for x, y in black:
        dist[x][y] = 0
        q.append((x, y))
    
    # Define the possible directions
    directions = [ (-1, -1), (-1, 0), (0, -1), (0, 1), (1, 0), (1, 1) ]
    
    while q:
        x, y = q.popleft()
        current_dist = dist[x][y]
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            # Check if the new coordinates are valid
            if 1 <= nx <= N and 1 <= ny <= nx:
                if current_dist + 1 < dist[nx][ny]:
                    dist[nx][ny] = current_dist + 1
                    q.append((nx, ny))
    
    # Precompute prefix sums for each row
    prefix = []
    for x in range(1, N + 1):
        row_prefix = [0] * (x + 1)
        for y in range(1, x + 1):
            row_prefix[y] = row_prefix[y - 1] + dist[x][y]
        prefix.append(row_prefix)
    
    count = 0
    for x in range(1, N + 1):
        max_s = N - x + 1
        if max_s < 1:
            continue
        for y in range(1, x + 1):
            current_sum = 0
            s_min = None
            for s in range(1, max_s + 1):
                r = x + s - 1
                # Check if r exceeds N (though shouldn't happen due to max_s)
                if r > N:
                    break
                start_col = y
                end_col = y + s - 1
                # Get the prefix sum for row r (remember prefix is 0-based for rows, rows are 1-based)
                row_prefix = prefix[r - 1]
                # Ensure end_col does not exceed the row's maximum y (r)
                if end_col > r:
                    end_col = r
                sum_row = row_prefix[end_col] - row_prefix[start_col - 1]
                current_sum += sum_row
                if current_sum >= P:
                    s_min = s
                    break  # Once found, no need to check larger s
            if s_min is not None:
                valid_s = max_s - s_min + 1
                count += valid_s
    print(count)

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