# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
236240 | VEGAnn | Retro (COCI17_retro) | C++14 | 93 ms | 56204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 310;
const int oo = 2e9;
char c[N][N];
short f[N][N][N], ans = 0, n, m;
void upd(short &x, short 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 >> 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;
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 stp = -1; stp < 2; stp++){
int ni = i + 1, nj = j + stp;
if (nj < 0 || nj >= m) continue;
if (c[ni][nj] == '*'){
if (sm == 0)
upd(ans, f[i][j][sm]);
} else if (c[ni][nj] == '.'){
upd(f[ni][nj][sm], f[i][j][sm]);
} else if (c[ni][nj] == '('){
upd(f[ni][nj][sm + 1], f[i][j][sm] + 1);
} else if (sm > 0){
upd(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 i = ans / 2; i > 0; i--)
cout << "()";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |