結果

問題 No.853 河原の石
ユーザー beet
提出日時 2019-07-26 22:30:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,065 bytes
コンパイル時間 2,363 ms
コンパイル使用メモリ 211,800 KB
最終ジャッジ日時 2025-01-07 08:12:16
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 RE * 21 TLE * 3 MLE * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
Int solve(Int h,Int w){
  vector<Int> cnt(w+1,0);
  cnt[0]=h;

  map<vector<Int>, Int> dp;
  queue< vector<Int> > que;
  dp[cnt]=0;
  que.emplace(cnt);
  while(!que.empty()){
    cnt=que.front();que.pop();
    for(Int i=0;i<w;i++){
      if(cnt[i]==0) continue;
      for(Int j=0;j<=w;j++){
        if(abs(i-j)>cnt[i]) continue;
        vector<Int> nxt=cnt;
        nxt[i]--;
        nxt[j]++;
        if(dp.count(nxt)) continue;
        dp[nxt]=dp[cnt]+1;
        que.emplace(nxt);
      }
    }
  }

  cnt.assign(w+1,0);
  cnt[w]=h;
  return dp[cnt];
}

signed main(){
  if(0){
    Int MAX = 10;
    for(Int h=1;h<=MAX;h++){
      for(Int w=1;w<=MAX*2;w++){
        cout<<setw(5)<<solve(h,w)-solve(h,w-1);
      }
      cout<<endl;
    }
  }
  Int h,w;
  cin>>h>>w;
  w=abs(w);
  cout<<solve(h,w)<<endl;
  return 0;
}
0