#pragma GCC optimize("Ofast") #include using namespace std; const int MAXN = 400; const int di[] = {0, -1, 0, 1}; const int dj[] = {1, 0, -1, 0}; int n, m; int a, c; vector> mat; int value[MAXN][MAXN]; int final_row, final_score = -1; vector> final; bool small = true, empty = true, samepoints = true, forfree = true; int sum; int tstart; #define ok(i, j) (i >= 0 && i < n && j >= 0 && j < m) template inline void apply(vector> mat, int row, const T& f) { int i = row, j = 0, dir = 0; while (ok(i, j)) { f(i, j, mat[i][j]); if (mat[i][j] == '/') dir ^= 1; else if (mat[i][j] == '\\') dir = 3 - dir; mat[i][j] = '.'; i += di[dir]; j += dj[dir]; } } inline int points(const vector>& mat, int row) { int res = 0; apply(mat, row, [&res](int i, int j, char){res += value[i][j];}); return res; } int _gpbio[MAXN][MAXN]; int _gpcookie; void getpath(const vector>& mat, int row, vector>& vpos) { ++_gpcookie; apply(mat, row, [&vpos](int i, int j, char) { if (_gpbio[i][j] != _gpcookie) { vpos.push_back({i, j}); _gpbio[i][j] = _gpcookie; } }); } void setsol(int x, int row, vector>& mat) { final_score = x; final_row = row; final = mat; // cerr< dp[i][j][dir]) { dp[i][j][dir] = x; put[i][j][dir] = '.'; } } if (dir == 0 || dir == 1) { int dir2 = dir ^ 1; int x = calc(i + di[dir2], j + dj[dir2], dir2); if (mat[i][j] == '.') x -= a; if (mat[i][j] == '\\') x -= c; x = max(x, 0); if (x > dp[i][j][dir]) { dp[i][j][dir] = x; put[i][j][dir] = '/'; } } if (dir == 0 || dir == 3) { int dir2 = 3 - dir; int x = calc(i + di[dir2], j + dj[dir2], dir2) - a; if (mat[i][j] == '.') x -= a; if (mat[i][j] == '/') x -= c; x = max(x, 0); if (x > dp[i][j][dir]) { dp[i][j][dir] = x; put[i][j][dir] = '\\'; } } return dp[i][j][dir] += value[i][j]; } void solve() { //((score, cost), ((row, idx), mat)) set, pair, vector>>>, greater, pair, vector>>>>> s; set, pair>> bio; for (int i = 0; i < n; ++i) { int x = points(mat, i); if (bio.insert({{x, 0}, {i, 0}}).second) { s.insert({{x, 0}, {{i, 0}, mat}}); } if (x > final_score) { setsol(x, i, mat); } } vector> mat2; for (int row = 0; row < n; ++row) { mat2 = mat; int x = calc(row, 0, 0); int i = row, j = 0, dir = 0; while (ok(i, j)) { mat2[i][j] = put[i][j][dir]; if (mat2[i][j] == '/') dir ^= 1; else if (mat2[i][j] == '\\') dir = 3 - dir; i += di[dir]; j += dj[dir]; } // int orig = points(mat2, row); // if (bio.insert({{x, orig - x}, {row, 0}}).second) // { // s.insert({{x, orig - x}, {{row, 0}, mat2}}); // } if (x > final_score) { setsol(x, row, mat2); } } int cost, row, idx, i, j, x, scr; vector> vpos; char prv; while (clock() - tstart < 4.6 * CLOCKS_PER_SEC && !s.empty()) { auto it = s.begin(); if (!small && !(empty && it->first.first < 1.3 * sum) && rand() % 5 == 0) advance(it, min((int) s.size() - 1, rand() % 10)); // cerr<first.first - it->first.second<first.first; cost = it->first.second; row = it->second.first.first; idx = it->second.first.second; mat2 = it->second.second; s.erase(it); vpos.clear(); getpath(mat2, row, vpos); for (; idx < vpos.size(); ++idx) { if (idx >= vpos.size() || clock() - tstart > 4.6 * CLOCKS_PER_SEC) break; tie(i, j) = vpos[idx]; prv = mat2[i][j]; mat2[i][j] = '/'; x = points(mat2, row); cost += a * (prv == '.') + c * (prv == '\\'); if (bio.insert({{x - cost, cost}, {row, idx + 1}}).second) s.insert({{x - cost, cost}, {{row, idx + 1}, mat2}}); while (s.size() * n * m > MAXSIZE) s.erase(prev(s.end())); if (x - cost > final_score) { setsol(x - cost, row, mat2); } cost -= a * (prv == '.') + c * (prv == '\\'); mat2[i][j] = '\\'; x = points(mat2, row); cost += a * (prv == '.') + c * (prv == '/'); if (bio.insert({{x - cost, cost}, {row, idx + 1}}).second) s.insert({{x - cost, cost}, {{row, idx + 1}, mat2}}); while (s.size() * n * m > MAXSIZE) s.erase(prev(s.end())); if (x - cost > final_score) { setsol(x - cost, row, mat2); } cost -= a * (prv == '.') + c * (prv == '/'); mat2[i][j] = prv; if (empty && scr < 1.3 * sum) break; if (!small) idx += rand() % int((vpos.size() - idx) / 2 + 1); } } } } int main() { tstart = clock(); srand(time(nullptr)); freopen("pinball.in", "r", stdin); freopen("pinball.out", "w", stdout); int i, j; cin>>n>>m>>a>>c; mat.resize(n, vector(m)); small = (n <= 10 && m <= 10); forfree = (a == 0 && c == 0); for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) { cin>>mat[i][j]; // mat[i][j] = '.'; if (mat[i][j] != '.') empty = false; } for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) { cin>>value[i][j]; // value[i][j] = 1; sum += value[i][j]; if (value[i][j] != (j ? value[i][j - 1] : (i ? value[i - 1][0] : value[i][j]))) samepoints = false; } // if (small && small::ACTIVE) // { // small::solve(); // } // else if (empty && empty::ACTIVE) // { // empty::solve(); // } // else if (samepoints && samepoints::ACTIVE) // { // samepoints::solve(); // } // else if (forfree && forfree::ACTIVE) // { // empty::solve(); // } // else { general::solve(); } cerr<<' '<