| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 236248 |
2020-05-31T19:23:00 Z |
VEGAnn |
Retro (COCI17_retro) |
C++14 |
|
140 ms |
61304 KB |
#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()
#define a3 array<int, 3>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 310;
const int oo = 2e9;
vector<a3> vc, vec[2];
queue<a3> q;
char c[N][N];
short f[N][N][N], ans = 0, n, m;
bool mrk[N][N][N], was[N][N][N];
void upd(short &x, short y){
x = max(x, y);
}
void check(int i, int j, int sm, int ni, int nj){
if (c[ni][nj] == '*'){
return;
} else if (c[ni][nj] == '.'){
if (mrk[ni][nj][sm] && f[i][j][sm] == f[ni][nj][sm] && !was[ni][nj][sm]){
was[ni][nj][sm] = 1;
q.push({ni, nj, sm});
}
} else if (c[ni][nj] == '('){
if (mrk[ni][nj][sm + 1] && f[i][j][sm] + 1 == f[ni][nj][sm + 1] && !was[ni][nj][sm + 1]){
was[ni][nj][sm + 1] = 1;
q.push({ni, nj, sm + 1});
}
} else {
if (sm > 0 && mrk[ni][nj][sm - 1] && f[i][j][sm] + 1 == f[ni][nj][sm - 1] && !was[ni][nj][sm - 1]){
was[ni][nj][sm - 1] = 1;
q.push({ni, nj, sm - 1});
}
}
}
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;
vc.PB({0, j, 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 j = 0; j < m; j++)
if (f[n - 1][j][0] == ans)
mrk[n - 1][j][0] = 1;
for (int i = n - 2; i >= 0; 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 && !mrk[i][j][sm]; stp++){
int ni = i + 1, nj = j + stp;
if (nj < 0 || nj >= m) continue;
if (c[ni][nj] == '*'){
if (sm == 0 && ans == f[i][j][sm])
mrk[i][j][sm] = 1;
} else if (c[ni][nj] == '.'){
if (mrk[ni][nj][sm] && f[i][j][sm] == f[ni][nj][sm])
mrk[i][j][sm] = 1;
} else if (c[ni][nj] == '('){
if (mrk[ni][nj][sm + 1] && f[i][j][sm] + 1 == f[ni][nj][sm + 1])
mrk[i][j][sm] = 1;
} else {
if (sm > 0 && mrk[ni][nj][sm - 1] && f[i][j][sm] + 1 == f[ni][nj][sm - 1])
mrk[i][j][sm] = 1;
}
}
}
}
for (int itr = 0; itr < ans; itr++){
vec[0].clear();
vec[1].clear();
for (a3 st : vc){
int i = st[0], j = st[1], sm = st[2];
for (int stp = -1; stp < 2; stp++){
int ni = i + 1, nj = j + stp;
if (nj < 0 || nj >= m) continue;
if (c[ni][nj] == '*') continue;
check(i, j, sm, ni, nj);
}
}
while (sz(q)){
a3 cr = q.front(); q.pop();
int i = cr[0], j = cr[1], sm = cr[2];
if (c[i][j] == '('){
vec[0].PB({i, j, sm});
continue;
}
if (c[i][j] == ')'){
vec[1].PB({i, j, sm});
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] == '*') continue;
check(i, j, sm, ni, nj);
}
}
if (sz(vec[0]) > 0){
cout << "(";
vc = vec[0];
} else {
cout << ")";
vc = vec[1];
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
640 KB |
Output is correct |
| 3 |
Correct |
5 ms |
640 KB |
Output is correct |
| 4 |
Correct |
5 ms |
768 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1536 KB |
Output is correct |
| 6 |
Correct |
8 ms |
4224 KB |
Output is correct |
| 7 |
Correct |
9 ms |
6016 KB |
Output is correct |
| 8 |
Correct |
8 ms |
3840 KB |
Output is correct |
| 9 |
Correct |
10 ms |
6272 KB |
Output is correct |
| 10 |
Correct |
12 ms |
7936 KB |
Output is correct |
| 11 |
Correct |
121 ms |
56952 KB |
Output is correct |
| 12 |
Correct |
111 ms |
55416 KB |
Output is correct |
| 13 |
Correct |
56 ms |
28664 KB |
Output is correct |
| 14 |
Correct |
57 ms |
26744 KB |
Output is correct |
| 15 |
Correct |
140 ms |
61276 KB |
Output is correct |
| 16 |
Correct |
114 ms |
59640 KB |
Output is correct |
| 17 |
Correct |
112 ms |
52344 KB |
Output is correct |
| 18 |
Correct |
96 ms |
50168 KB |
Output is correct |
| 19 |
Correct |
131 ms |
59000 KB |
Output is correct |
| 20 |
Correct |
117 ms |
61304 KB |
Output is correct |
