Submission #239771

#TimeUsernameProblemLanguageResultExecution timeMemory
239771NONAMERetro (COCI17_retro)C++14
85 / 100
158 ms115960 KiB
#include <iostream> #include <vector> #include <set> #include <array> #include <queue> using namespace std; typedef long long ll; typedef long double ld; const int N = 3e2 + 10; const int base = 1e9 + 7; vector <array <int, 3> > vc[2], v; queue <array <int, 3> > q; char c[N][N]; int f[N][N][N], ans = 0, n, m; bool mrk[N][N][N], was[N][N][N]; void check(int i, int j, int sm, int ni, int nj) { if (c[ni][nj] == '*') return; if (c[ni][nj] == '.') { if (mrk[ni][nj][sm] && f[i][j][sm] == f[ni][nj][sm] && !was[ni][nj][sm]) { was[ni][nj][sm] = 1; q.push({ni, nj, sm}); } } else if (c[ni][nj] == '(') { if (mrk[ni][nj][sm + 1] && f[i][j][sm] + 1 == f[ni][nj][sm + 1] && !was[ni][nj][sm]) { was[ni][nj][sm + 1] = 1; q.push({ni, nj, sm + 1}); } } else { if (sm > 0 && mrk[ni][nj][sm - 1] && f[i][j][sm] + 1 == f[ni][nj][sm - 1] && !was[ni][nj][sm - 1]) { was[ni][nj][sm - 1] = 1; q.push({ni, nj, sm - 1}); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> c[n - 1 - i][j]; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) for (int sm = 0; sm <= i; ++sm) f[i][j][sm] = -1; for (int j = 0; j < m; ++j) if (c[0][j] == 'M') { f[0][j][0] = 0; v.push_back({0, j, 0}); } for (int i = 0; i < n - 1; ++i) for (int j = 0; j < m; ++j) for (int sm = 0; sm <= i; ++sm) { if (f[i][j][sm] < 0) continue; for (int s = -1; s < 2; ++s) { int ni = i + 1, nj = j + s; if (ni < 0 || nj >= m) continue; if (c[ni][nj] == '*') { if (sm == 0) ans = max(ans, f[i][j][sm]); } else if (c[ni][nj] == '.') f[ni][nj][sm] = max(f[ni][nj][sm], f[i][j][sm]); else if (c[ni][nj] == '(') f[ni][nj][sm + 1] = max(f[ni][nj][sm + 1], f[i][j][sm] + 1); else if (sm > 0) f[ni][nj][sm - 1] = max(f[ni][nj][sm - 1], f[i][j][sm] + 1); } } for (int j = 0; j < m; ++j) ans = max(ans, f[n - 1][j][0]); cout << ans << "\n"; for (int j = 0; j < m; ++j) if (f[n - 1][j][0] == ans) mrk[n - 1][j][0] = 1; for (int i = n - 2; i >= 0; --i) for (int j = 0; j < m; ++j) for (int sm = 0; sm <= i; ++sm) { if (f[i][j][sm] < 0) continue; for (int s = -1; s < 2 && !mrk[i][j][sm]; ++s) { int ni = i + 1, nj = j + s; if (nj < 0 || nj >= m) continue; if (c[ni][nj] == '*') { if (sm == 0 && ans == f[i][j][sm]) mrk[i][j][sm] = 1; } else if (c[ni][nj] == '.') { if (mrk[ni][nj][sm] && f[i][j][sm] == f[ni][nj][sm]) mrk[i][j][sm] = 1; } else if (c[ni][nj] == '(') { if (mrk[ni][nj][sm + 1] && f[i][j][sm] + 1 == f[ni][nj][sm + 1]) mrk[i][j][sm] = 1; } else { if (sm > 0 && mrk[ni][nj][sm - 1] && f[i][j][sm] + 1 == f[ni][nj][sm - 1]) mrk[i][j][sm] = 1; } } } while (ans--) { vc[0].clear(); vc[1].clear(); for (auto st : v) { int i = st[0], j = st[1], sm = st[2]; for (int s = -1; s < 2; ++s) { int ni = i + 1, nj = j + s; if (nj < 0 || nj >= m) continue; if (c[ni][nj] == '*') continue; check(i, j, sm, ni, nj); } } while (!q.empty()) { auto cr = q.front(); q.pop(); int i = cr[0], j = cr[1], sm = cr[2]; if (c[i][j] == '(') { vc[0].push_back({i, j, sm}); continue; } if (c[i][j] == ')') { vc[1].push_back({i, j, sm}); continue; } for (int s = -1; s < 2; ++s) { int ni = i + 1, nj = j + s; if (nj < 0 || nj >= m) continue; if (c[ni][nj] == '*') continue; check(i, j, sm, ni, nj); } } if (!vc[0].empty()) { cout << "("; v = vc[0]; } else { cout << ")"; v = vc[1]; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...