Submission #236122

#TimeUsernameProblemLanguageResultExecution timeMemory
236122VEGAnnRetro (COCI17_retro)C++14
5 / 100
904 ms15300 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define a3 array<int, 3> using namespace std; const int N = 310; const int oo = 2e9; string ans = "", f[2][N][N], t; char s[N][N]; int n, m; bool better(string &nw, string &old){ return (sz(nw) > sz(old) || (sz(nw) == sz(old) && nw < old)); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef _LOCAL freopen("in.txt","r",stdin); #endif // _LOCAL cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> s[n - 1 - i][j]; for (int j = 0; j < m; j++) if (s[0][j] == 'M') f[0][j][0] = ""; else f[0][j][0] = ")"; for (int i = 0, tp = 0; i < n - 1; i++, tp ^= 1){ for (int j = 0; j < m; j++) for (int sm = 0; sm <= i + 1; sm++) f[tp ^ 1][j][sm] = ")"; for (int j = 0; j < m; j++) for (int sm = 0; sm <= i; sm++){ if (f[tp][j][sm] == ")") continue; for (int stp = -1; stp < 2; stp++){ int ni = i + 1, nj = j + stp; if (nj < 0 || nj >= m) continue; if (s[ni][nj] == '*'){ if (sm == 0){ if (better(f[tp][j][sm], ans)) ans = f[tp][j][sm]; } } else if (s[ni][nj] == '.'){ if (f[tp][j][sm] < f[tp ^ 1][nj][sm]) f[tp ^ 1][nj][sm] = f[tp][j][sm]; } else if (s[ni][nj] == '('){ t = f[tp][j][sm] + "("; if (t < f[tp ^ 1][nj][sm + 1]) f[tp ^ 1][nj][sm + 1] = t; } else if (s[ni][nj] == ')'){ if (sm == 0) continue; t = f[tp][j][sm] + ")"; // cerr << t << '\n' << f[tp ^ 1][nj][sm - 1] << '\n'; if (t < f[tp ^ 1][nj][sm - 1]) f[tp ^ 1][nj][sm - 1] = t; } } } } int tp = (n - 1) % 2; for (int j = 0; j < m; j++) if (f[tp][j][0] != ")" && better(f[tp][j][0], ans)) ans = f[tp][j][0]; cout << sz(ans) << '\n' << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...