結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2020-03-19 22:28:46 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 986 bytes |
コンパイル時間 | 645 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 518,564 KB |
最終ジャッジ日時 | 2024-12-14 03:36:34 |
合計ジャッジ時間 | 104,246 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 MLE * 1 |
other | AC * 2 TLE * 13 MLE * 7 |
ソースコード
#!/usr/bin/ python3.8import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesimport numpy as npH, 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) * INFfor n in range(1, H):np.minimum(dp[n - 1] + 1, dp[n], out=dp[n])for n in range(1, W):np.minimum(dp[:, n - 1] + 1, dp[:, n], out=dp[:, n])np.minimum(dp[:-1, n - 1] + 1, dp[1:, n], out=dp[1:, n])return dpdp = 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 - lowanswer = np.maximum(x, 0).sum()print(answer)