結果

問題 No.866 レベルKの正方形
ユーザー tonetone
提出日時 2019-08-22 01:10:34
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,800 bytes
コンパイル時間 988 ms
コンパイル使用メモリ 88,272 KB
実行使用メモリ 419,328 KB
最終ジャッジ日時 2024-10-10 19:45:47
合計ジャッジ時間 42,241 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 3,205 ms
419,328 KB
testcase_09 AC 2,725 ms
419,200 KB
testcase_10 AC 2,512 ms
419,072 KB
testcase_11 AC 3,117 ms
419,200 KB
testcase_12 AC 2,671 ms
419,328 KB
testcase_13 AC 3,110 ms
419,200 KB
testcase_14 WA -
testcase_15 AC 2,983 ms
419,200 KB
testcase_16 AC 2,913 ms
419,328 KB
testcase_17 AC 2,788 ms
419,072 KB
testcase_18 AC 2,984 ms
419,328 KB
testcase_19 WA -
testcase_20 AC 2,857 ms
419,328 KB
testcase_21 AC 1,615 ms
419,200 KB
testcase_22 AC 1 ms
6,816 KB
testcase_23 AC 2 ms
6,820 KB
testcase_24 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int H, W, K;
  scanf("%d %d %d", &H, &W, &K);
  std::vector<string> c(H);
  for(int i=0;i<H;i++) std::cin >> c[i];
  vvi dp = vv(H, 26*W, 0, int);
  for(int i=0;i<26;i++){
    dp[H-1][W-1+i*W] = (c[H-1][W-1]-'a'==i?1:-1);
    for(int j=0;j<H;j++){
      for(int k=0;k<W;k++){
        if(j==0&&k==0) continue;
        if(c[H-1-j][W-1-k]-'a'==i) dp[H-1-j][W-1-k+i*W] = 1;
        else if(j==0) dp[H-1-j][W-1-k + i*W] = (dp[H-1-j][W-k+i*W]==-1?-1:dp[H-1-j][W-k+i*W]+1);
        else if(k==0) dp[H-1-j][W-1-k+i*W] = (dp[H-j][W-1-k+i*W]==-1?-1:dp[H-j][W-1-k+i*W]+1);
        else {
          if(max({dp[H-j][W-1-k+i*W], dp[H-1-j][W-k+i*W], dp[H-j][W-k+i*W]})==-1) dp[H-1-j][W-1-k+i*W]=-1;
          else dp[H-1-j][W-1-k+i*W] = min({(dp[H-j][W-1-k+i*W]==-1?1000000007:dp[H-j][W-1-k+i*W]+1),
             (dp[H-1-j][W-k+i*W]==-1?1000000007:dp[H-1-j][W-k+i*W]+1), (dp[H-j][W-k+i*W]==-1?1000000007:dp[H-j][W-k+i*W]+1)});
        }
        if(dp[H-1-j][W-1-k+i*W]!=-1&&(j+1<dp[H-1-j][W-1-k+i*W]||k+1<dp[H-1-j][W-1-k+i*W])) dp[H-1-j][W-1-k+i*W]=-1;
      }
    }
  }
  ll ans = 0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      std::vector<int> las(26);
      for(int k=0;k<26;k++) las[k] = (dp[i][j+k*W]==-1?1000000007:dp[i][j+k*W]);
      sort(las.begin(), las.end());
      if(las[K-1]==1000000007) continue;
      ans += min({H-i + 1, W-j+ 1, las[K]}) - las[K-1] ;
    }
  }
  printf("%lld\n", ans);
  return 0;
}
0