Submission #643487

#TimeUsernameProblemLanguageResultExecution timeMemory
643487BackNoobRetro (COCI17_retro)C++14
40 / 100
114 ms113648 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define endl '\n' #define MASK(i) (1LL << (i)) #define ull unsigned long long #define ld long double #define pb push_back #define all(x) (x).begin() , (x).end() #define BIT(x , i) ((x >> (i)) & 1) #define TASK "task" #define sz(s) (int) (s).size() using namespace std; const int mxN = 1e6 + 227; const int inf = 1e9 + 277; const int mod = 1e9 + 7; const ll infll = 1e18 + 7; const int base = 307; const int LOG = 20; template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } int n; int m; char a[307][307]; int dp[307][307][307]; void solve() { cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> a[i][j]; pair<int, int> pos; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(a[i][j] == 'M') pos = make_pair(i, j); memset(dp, -0x3f, sizeof(dp)); int res = 0; dp[pos.fi][pos.se][0] = 0; for(int i = n; i > 1; i--) { for(int j = 1; j <= m; j++) { for(int k = 0; k <= n; k++) { if(dp[i][j][k] == dp[0][0][0]) continue; for(int d = -1; d <= 1; d++) { if(j + d >= 1 && j + d <= m) { if(a[i - 1][j + d] == '*') { if(k == 0) maximize(res, dp[i][j][k]); continue; } if(a[i - 1][j + d] == '(') { maximize(dp[i - 1][j + d][k + 1], dp[i][j][k] + 1); } if(a[i - 1][j + d] == ')') { if(k > 0) maximize(dp[i - 1][j + d][k - 1], dp[i][j][k] + 1); } if(a[i - 1][j + d] == '.') { maximize(dp[i - 1][j + d][k], dp[i][j][k]); } } } } } } for(int j = 1; j <= m; j++) maximize(res, dp[1][j][0]); cout << res << endl; for(int j = 0; j < res; j++) cout << '('; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen("graph.inp", "r", stdin); //freopen("graph.out", "w", stdout); int tc = 1; //cin >> tc; while(tc--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...