結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー tone
提出日時 2019-08-22 00:51:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,115 bytes
コンパイル時間 1,134 ms
コンパイル使用メモリ 91,348 KB
実行使用メモリ 818,304 KB
最終ジャッジ日時 2024-10-10 18:50:30
合計ジャッジ時間 6,615 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 MLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

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 vvv(a, b, c, d, e) vector<vector<vector<e> > >(a, vector<vector<e> >(b, vector<e> (c, d)))
#define vvvl vector<vector<vector<ll> > >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll H, W, K;
  std::cin >> H >> W >> K;
  std::vector<string> c(H);
  for(int i=0;i<H;i++) std::cin >> c[i];
  vvvl dp = vvv(H, W, 26, 0, ll);

  for(int i=0;i<26;i++){
    dp[H-1][W-1][i] = (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] = 1;
        else if(j==0) dp[H-1-j][W-1-k][i] = (dp[H-1-j][W-k][i]==-1?-1:dp[H-1-j][W-k][i]+1);
        else if(k==0) dp[H-1-j][W-1-k][i] = (dp[H-j][W-1-k][i]==-1?-1:dp[H-j][W-1-k][i]+1);
        else {
          if(max({dp[H-j][W-1-k][i], dp[H-1-j][W-k][i], dp[H-j][W-k][i]})==-1) dp[H-1-j][W-1-k][i]=-1;
          else dp[H-1-j][W-1-k][i] = min({(dp[H-j][W-1-k][i]==-1?1000000007:dp[H-j][W-1-k][i]+1),
             (dp[H-1-j][W-k][i]==-1?1000000007:dp[H-1-j][W-k][i]+1), (dp[H-j][W-k][i]==-1?1000000007:dp[H-j][W-k][i]+1)});
        }
        if(dp[H-1-j][W-1-k][i]!=-1&&(j+1<dp[H-1-j][W-1-k][i]||k+1<dp[H-1-j][W-1-k][i])) dp[H-1-j][W-1-k][i]=-1;
      }
    }
  }
  ll ans = 0;
  std::vector<ll> las(26);
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      for(int k=0;k<26;k++) las[k] = (dp[i][j][k]==-1?1000000007:dp[i][j][k]);
      sort(las.begin(), las.end());
      if(las[K-1]==1000000007) continue;
      //for(int l = 0;l<K+1;l++) std::cout << las[l] << " ";
      //std::cout << min({H-i + 1, W-j + 1, las[K]}) - las[K-1]<< '\n';
      //std::cout << min({H-i, W-j, las[K]}) << " " << las[K-1] << '\n';
      ans += min({H-i + 1, W-j+ 1, las[K]}) - las[K-1] ;
    }
  }
  std::cout << ans << '\n';

  return 0;
}
0