Submission #236129

#TimeUsernameProblemLanguageResultExecution timeMemory
236129VEGAnnRetro (COCI17_retro)C++14
50 / 100
56 ms7288 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, ff[2][N][N], an = 0; bool better(string &nw, string &old){ return (sz(nw) > sz(old) || (sz(nw) == sz(old) && nw < old)); } void upd(int &x, int y){ x = max(x, y); } 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]; if (n > 100) { for (int j = 0; j < m; j++) if (s[0][j] == 'M') ff[0][j][0] = 0; else ff[0][j][0] = -1; 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++) ff[tp ^ 1][j][sm] = -1; for (int j = 0; j < m; j++) for (int sm = 0; sm <= i; sm++){ if (ff[tp][j][sm] == -1) 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){ an = max(an, ff[tp][j][sm]); } } else if (s[ni][nj] == '.'){ upd(ff[tp ^ 1][nj][sm], ff[tp][j][sm]); } else if (s[ni][nj] == '('){ upd(ff[tp ^ 1][nj][sm + 1], ff[tp][j][sm] + 1); } else if (s[ni][nj] == ')'){ if (sm == 0) continue; upd(ff[tp ^ 1][nj][sm - 1], ff[tp][j][sm] + 1); } } } } int tp = (n - 1) % 2; for (int j = 0; j < m; j++) upd(an, ff[tp][j][0]); cout << an << '\n'; for (int i = 0; i < an / 2; i++) cout << "("; for (int i = 0; i < an / 2; i++) cout << ")"; } else { 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 ^ 1][nj][sm] == ")" || better(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 (f[tp ^ 1][nj][sm + 1] == ")" || better(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 (f[tp ^ 1][nj][sm - 1] == ")" || better(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...