Submission #236088

#TimeUsernameProblemLanguageResultExecution timeMemory
236088NONAMERetro (COCI17_retro)C++17
0 / 100
251 ms524292 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define sz(x) int(x.size()) #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #define N 100500 #define oo ll(1e16) #define ft first #define sd second #define pb push_back #define ppb pop_back #define el '\n' #define elf endl #define base ll(1e9 + 7) using namespace std; typedef long long ll; typedef long double ld; int n, m, f[300][300][300]; string s[N], fs[300][300][300]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) cin >> s[i]; for (int i = 0; i < n - i - 1; i++) swap(s[i], s[n - i - 1]); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < n; k++) f[i][j][k] = -1; for (int i = 0; i < m; i++) if (s[0][i] == 'M') f[0][i][0] = 0; for (int i = 0; i < n - 1; i++) for (int j = 0; j < m; j++) { if (s[i][j] == '*') continue; if (j - 1 >= 0 && s[i + 1][j - 1] != '*') { if (s[i + 1][j - 1] == '.') { for (int k = 0; k < n; k++) if (f[i][j][k] != -1) { if (f[i][j][k] > f[i + 1][j - 1][k]) { f[i + 1][j - 1][k] = f[i][j][k]; fs[i + 1][j - 1][k] = fs[i][j][k]; } else if (f[i][j][k] == f[i + 1][j - 1][k]) { fs[i + 1][j - 1][k] = min(fs[i + 1][j - 1][k], fs[i][j][k]); } } } else { if (s[i + 1][j - 1] == '(') { for (int k = 0; k < n - 1; k++) if (f[i][j][k] != -1) { if (f[i][j][k] + 1 > f[i + 1][j - 1][k + 1]) { f[i + 1][j - 1][k + 1] = f[i][j][k] + 1; fs[i + 1][j - 1][k + 1] = fs[i][j][k] + '('; } else if (f[i][j][k] + 1 == f[i + 1][j - 1][k + 1]) { fs[i + 1][j - 1][k + 1] = min(fs[i + 1][j - 1][k + 1], fs[i][j][k] + '('); } } } else { for (int k = 1; k < n; k++) if (f[i][j][k] != -1) { if (f[i][j][k] + 1 > f[i + 1][j - 1][k - 1]) { f[i + 1][j - 1][k - 1] = f[i][j][k] + 1; fs[i + 1][j - 1][k - 1] = fs[i][j][k] + ')'; } else if (f[i][j][k] + 1 == f[i + 1][j - 1][k - 1]) { fs[i + 1][j - 1][k - 1] = min(fs[i + 1][j - 1][k - 1], fs[i][j][k] + ')'); } } } } } if (s[i + 1][j] != '*') { if (s[i + 1][j] == '.') { for (int k = 0; k < n; k++) if (f[i][j][k] != -1) { if (f[i][j][k] > f[i + 1][j][k]) { f[i + 1][j][k] = f[i][j][k]; fs[i + 1][j][k] = fs[i][j][k]; } else if (f[i][j][k] == f[i + 1][j][k]) { fs[i + 1][j][k] = min(fs[i + 1][j][k], fs[i][j][k]); } } } else { if (s[i + 1][j] == '(') { for (int k = 0; k < n; k++) if (f[i][j][k] != -1) { if (f[i][j][k] + 1 > f[i + 1][j][k + 1]) { f[i + 1][j][k + 1] = f[i][j][k] + 1; fs[i + 1][j][k + 1] = fs[i][j][k] + '('; } else if (f[i][j][k] + 1 == f[i + 1][j][k + 1]) { fs[i + 1][j][k + 1] = min(fs[i + 1][j][k + 1], fs[i][j][k] + '('); } } } else { for (int k = 1; k < n; k++) if (f[i][j][k] != -1) { if (f[i][j][k] + 1 > f[i + 1][j][k - 1]) { f[i + 1][j][k - 1] = f[i][j][k] + 1; fs[i + 1][j][k - 1] = fs[i][j][k] + ')'; } else if (f[i][j][k] + 1 == f[i + 1][j][k - 1]) { fs[i + 1][j][k - 1] = min(fs[i + 1][j][k - 1], fs[i][j][k] + ')'); } } } } } if (j + 1 < m && s[i + 1][j + 1] != '*') { if (s[i + 1][j + 1] == '.') { for (int k = 0; k < n; k++) if (f[i][j][k] != -1) { if (f[i][j][k] > f[i + 1][j + 1][k]) { f[i + 1][j + 1][k] = f[i][j][k]; fs[i + 1][j + 1][k] = fs[i][j][k]; } else if (f[i][j][k] == f[i + 1][j + 1][k]) { fs[i + 1][j + 1][k] = min(fs[i + 1][j + 1][k], fs[i][j][k]); } } } else { if (s[i + 1][j + 1] == '(') { for (int k = 0; k < n; k++) if (f[i][j][k] != -1) { if (f[i][j][k] + 1 > f[i + 1][j + 1][k + 1]) { f[i + 1][j + 1][k + 1] = f[i][j][k] + 1; fs[i + 1][j + 1][k + 1] = fs[i][j][k] + '('; } else if (f[i][j][k] + 1 == f[i + 1][j + 1][k + 1]) { fs[i + 1][j + 1][k + 1] = min(fs[i + 1][j + 1][k + 1], fs[i][j][k] + '('); } } } else { for (int k = 1; k < n; k++) if (f[i][j][k] != -1) { if (f[i][j][k] + 1 > f[i + 1][j + 1][k - 1]) { f[i + 1][j + 1][k - 1] = f[i][j][k] + 1; fs[i + 1][j + 1][k - 1] = fs[i][j][k] + ')'; } else if (f[i][j][k] + 1 == f[i + 1][j + 1][k - 1]) { fs[i + 1][j + 1][k - 1] = min(fs[i + 1][j + 1][k - 1], fs[i][j][k] + ')'); } } } } } } int x = 0, y = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (f[i][j][0] > f[x][y][0]) x = i, y = j; cout << f[x][y][0] << el << fs[x][y][0]; }

Compilation message (stderr)

retro.cpp: In function 'int main()':
retro.cpp:155:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < n; i++)
     ^~~
retro.cpp:160:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  cout << f[x][y][0] << el << fs[x][y][0];
  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...