#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; using lint = long long int; using P = pair; using PL = pair; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) #define ALL(a) (a).begin(),(a).end() constexpr int MOD = 1000000007; constexpr lint B1 = 1532834020; constexpr lint M1 = 2147482409; constexpr lint B2 = 1388622299; constexpr lint M2 = 2147478017; constexpr int INF = 2147483647; void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";} templatevoid chmax(T &a, const T &b) { if (avoid chmin(T &a, const T &b) { if (b> H >> W; vector UDRL(4); REP(i, 4) cin >> UDRL[i]; lint K, P; cin >> K >> P; int xs, ys, xt, yt; cin >> xs >> ys >> xt >> yt; xs--;ys--;xt--;yt--; vector C(H); REP(i, H) cin >> C[i]; vector> dp(H, vector(W, 1e18)); dp[xs][ys] = 0; set> st; st.insert(make_tuple(0, xs, ys)); vector dx = {-1, 1, 0, 0}; vector dy = {0, 0, 1, -1}; while(!st.empty()) { auto a = *st.begin(); st.erase(a); lint d = get<0>(a); lint x = get<1>(a); lint y = get<2>(a); if(dp[x][y] != d) continue; REP(k, 4) { lint nx = x + dx[k]; lint ny = y + dy[k]; if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue; if(C[nx][ny] == '#') continue; lint nd = d + UDRL[k] + (C[nx][ny] == '@' ? P : 0); if(nd < dp[nx][ny]) { dp[nx][ny] = nd; st.insert(make_tuple(nd, nx, ny)); } } } //cout << dp[xt][yt] << endl; yes(dp[xt][yt] <= K); }