提出 #41204876

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector<string> s(N);
  for (auto &t : s) cin >> t;
  
  int MOD = M+1;

  vector<vector<ll>> dp(MOD, vector<ll>(N+1, INF));
  dp[1][0] = 0;

  for (int i = 1; i < N; i++){
    for (int j = 0; j <= N; j++){
      if (dp[i%MOD][j] == INF) continue;

      for (int k = 0; k < M; k++){
	if (s[i-1][k] == '1'){
	  int ni = i + k + 1;
	  if (ni <= N){
	    chmin(dp[ni%MOD][j], dp[i%MOD][j] + 1);
	    for (int nj = i + 1; nj <= i + k; nj++){
	      chmin(dp[ni%MOD][nj], dp[i%MOD][j] + 1);
	    }
	  }
	}
      }
    }

    for (auto &t : dp[i%MOD]) t = INF;
  }
  
  for (int i = 2; i < N; i++){
    ll dist = dp[N%MOD][i];
    if (dist == INF) { cout << -1 << " "; }
    else { cout << dist << " "; }
  }
  cout << endl;
  
  return 0;
}

提出情報

ジャッジ結果