結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2020-07-04 17:34:48 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 971 bytes |
コンパイル時間 | 126 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 501,084 KB |
最終ジャッジ日時 | 2024-09-19 05:40:05 |
合計ジャッジ時間 | 16,078 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 TLE * 1 |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np H, W, K = map(int, readline().split()) C = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] INF = np.int32(10 ** 5) def calc_alphabet(a): dp = (C != a) * INF for n in range(1, H): np.minimum(dp[n - 1] + 1, dp[n], out=dp[n]) dp = dp.T.copy() for n in range(1, W): np.minimum(dp[n - 1] + 1, dp[n], out=dp[n]) np.minimum(dp[n-1,:-1] + 1, dp[n,1:], out=dp[n,1:]) return dp.T dp = np.empty((26, H, W), np.int32) for i in range(26): a = chr(ord('a') + i).encode() dp[i] = calc_alphabet(a) dp.sort(axis=0) low = dp[K - 1] if K == 26: high = np.full_like(low, INF) else: high = dp[K] for n in range(min(H, W)): np.minimum(high[n, n:], n + 1, out=high[n, n:]) np.minimum(high[n:, n], n + 1, out=high[n:, n]) x = high - low answer = np.maximum(x, 0).sum() print(answer)