結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-19 17:49:15 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,918 ms / 6,000 ms |
コード長 | 1,588 bytes |
コンパイル時間 | 682 ms |
コンパイル使用メモリ | 88,020 KB |
実行使用メモリ | 414,452 KB |
最終ジャッジ日時 | 2024-10-04 16:57:17 |
合計ジャッジ時間 | 23,716 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:53:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 53 | scanf("%d%d%d", &h, &w, &k); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp:54:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 54 | for (int i = 0; i < h; i++) scanf("%s", flds[i]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 866.cc: No.866 レベルKの正方形 - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_H = 2000;const int MAX_W = 2000;const int INF = 1 << 29;/* typedef */typedef long long ll;/* global variables */char flds[MAX_H][MAX_W + 4];int dp[MAX_H + 1][MAX_W + 1][26];/* subroutines */inline int min3(int a, int b, int c) {if (a < b) return (a < c) ? a : c;return (b < c) ? b : c;}/* main */int main() {int h, w, k;scanf("%d%d%d", &h, &w, &k);for (int i = 0; i < h; i++) scanf("%s", flds[i]);for (int i = h; i >= 0; i--)for (int j = w; j >= 0; j--) {if (i == h || j == w)fill(dp[i][j], dp[i][j] + 26, INF);else {int cij = flds[i][j] - 'a';for (int c = 0; c < 26; c++) {if (c == cij)dp[i][j][c] = 1;elsedp[i][j][c] =min3(dp[i][j + 1][c], dp[i + 1][j][c], dp[i + 1][j + 1][c])+ 1;}}}ll sum = 0;for (int i = 0; i < h; i++)for (int j = 0; j < w; j++) {int *as = dp[i][j];sort(as, as + 26);int maxl = min(h - i, w - j);int a0 = as[k - 1];if (a0 <= maxl) {int a1 = min(maxl + 1, (k >= 26) ? INF : as[k]);sum += a1 - a0;}}printf("%lld\n", sum);return 0;}