結果

問題 No.655 E869120 and Good Triangles
ユーザー qwewe
提出日時 2025-04-24 12:31:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,135 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 357,904 KB
最終ジャッジ日時 2025-04-24 12:33:15
合計ジャッジ時間 4,779 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())
    blacks = []
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        blacks.append((x, y))
    
    # Initialize a[i][j] (1-based)
    INF = float('inf')
    a = [[INF] * (i + 1) for i in range(N + 1)]
    q = deque()
    for x, y in blacks:
        a[x][y] = 0
        q.append((x, y))
    
    # Directions: up-left, up, left, right, down-left, down-right
    directions = [(-1, -1), (-1, 0), (0, -1), (0, 1), (1, 0), (1, 1)]
    
    while q:
        i, j = q.popleft()
        for di, dj in directions:
            ni = i + di
            nj = j + dj
            if ni < 1 or ni > N:
                continue
            if nj < 1 or nj > ni:
                continue
            if a[ni][nj] > a[i][j] + 1:
                a[ni][nj] = a[i][j] + 1
                q.append((ni, nj))
    
    # Compute row-wise prefix sums
    prefix = [[0] * (i + 1) for i in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            prefix[i][j] = prefix[i][j - 1] + a[i][j]
    
    # Compute row_prefix_sum[j][i] = sum of prefix[1][j] to prefix[i][j]
    row_prefix_sum = [[0] * (N + 1) for _ in range(N + 2)]
    for j in range(0, N + 1):
        current = 0
        for i in range(0, N + 1):
            if i == 0:
                row_prefix_sum[j][i] = 0
            else:
                if j <= i and j >= 0:
                    current += prefix[i][j]
                row_prefix_sum[j][i] = current
    
    # Compute diagonal_prefix_sum
    diagonal_prefix_sum = {}
    max_c = - (N - 1)
    for c in range(-(N - 1), 1):
        diagonal_prefix_sum[c] = [0] * (N + 1)
        current = 0
        for i in range(1, N + 1):
            j = i + c
            if 1 <= j <= i:
                current += prefix[i][j]
            else:
                current += 0
            diagonal_prefix_sum[c][i] = current
    
    total = 0
    for x in range(1, N + 1):
        for y in range(1, x + 1):
            max_s = N - x + 1
            if max_s < 1:
                continue
            c = y - x
            # Binary search for minimal s where sum >= P
            low = 1
            high = max_s
            ans = None
            while low <= high:
                mid = (low + high) // 2
                s = mid
                end_i = x + s - 1
                if end_i > N:
                    high = mid - 1
                    continue
                # Calculate sum_part1 and sum_part2
                sum_part1 = diagonal_prefix_sum.get(c, [0]*(N+1))[end_i] - diagonal_prefix_sum.get(c, [0]*(N+1))[x-1]
                sum_part2 = row_prefix_sum[y-1][end_i] - row_prefix_sum[y-1][x-1]
                current_sum = sum_part1 - sum_part2
                if current_sum >= P:
                    ans = mid
                    high = mid - 1
                else:
                    low = mid + 1
            if ans is not None:
                total += max_s - ans + 1
    print(total)

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