# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
635300 |
2022-08-26T00:23:36 Z |
racsosabe |
Retro (COCI17_retro) |
C++14 |
|
229 ms |
524288 KB |
#include<bits/stdc++.h>
using namespace::std;
const int N = 300 + 5;
const int inf = 1e9;
int n;
int m;
char s[N][N];
bool vis[N][N][N];
int memo[N][N][N];
string ans[N][N][N];
pair<int, int> nxt[N][N][N];
vector<pair<int, int>> G[N][N][N];
bool check_bomb(int i, int j){
return s[i - 1][j] == '*' or (j and s[i - 1][j - 1] == '*') or (j + 1 < m and s[i - 1][j + 1] == '*');
}
int DP(int i, int j, int prefix){
if(i == 0) return memo[i][j][prefix] = prefix == 0 ? 0 : -inf;
if(vis[i][j][prefix]) return memo[i][j][prefix];
int ans = -inf;
for(int dx = -1; dx <= 1; dx++){
int cand = -inf;
if(j + dx >= 0 and j + dx < m){
if(s[i - 1][j + dx] == '*') cand = prefix ? -inf : 0;
else if(s[i - 1][j + dx] == '(') cand = 1 + DP(i - 1, j + dx, prefix + 1);
else if(s[i - 1][j + dx] == ')' and prefix) cand = 1 + DP(i - 1, j + dx, prefix - 1);
else if(s[i - 1][j + dx] == '.') cand = DP(i - 1, j + dx, prefix);
}
ans = max(ans, cand);
}
vis[i][j][prefix] = true;
return memo[i][j][prefix] = ans;
}
string get_ans(int i, int j, int prefix){
if(i == 0 or s[i][j] == '*') return "";
if(vis[i][j][prefix]) return ans[i][j][prefix];
string res = "*";
int best;
for(int dx = -1; dx <= 1; dx++){
if(j + dx < 0 or j + dx >= m) continue;
int cand = -inf;
string cur = "";
int new_prefix = prefix;
if(s[i - 1][j + dx] == '*') cand = prefix ? -inf : 0;
else if(s[i - 1][j + dx] == '('){
cur.push_back('(');
new_prefix++;
cand = 1 + memo[i - 1][j + dx][prefix + 1];
}
else if(s[i - 1][j + dx] == ')' and prefix){
cur.push_back(')');
new_prefix--;
cand = 1 + memo[i - 1][j + dx][prefix - 1];
}
else if(s[i - 1][j + dx] == '.') cand = memo[i - 1][j + dx][prefix];
if(cand != memo[i][j][prefix]) continue;
cur += get_ans(i - 1, j + dx, new_prefix);
if(res > cur){
res = cur;
best = dx;
}
}
vis[i][j][prefix] = true;
return ans[i][j][prefix] = res;
}
int main(){
scanf("%d %d", &n, &m);
int sy;
for(int i = 0; i < n; i++){
scanf("%s", s[i]);
for(int j = 0; j < m; j++){
if(s[i][j] == 'M') sy = j;
}
}
printf("%d\n", DP(n - 1, sy, 0));
memset(vis, 0, sizeof vis);
if(n <= 100) printf("%s\n", get_ans(n - 1, sy, 0).c_str());
else puts("A");
return 0;
}
Compilation message
retro.cpp: In function 'std::string get_ans(int, int, int)':
retro.cpp:42:6: warning: variable 'best' set but not used [-Wunused-but-set-variable]
42 | int best;
| ^~~~
retro.cpp: In function 'int main()':
retro.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
retro.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%s", s[i]);
| ~~~~~^~~~~~~~~~~~
retro.cpp:80:8: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
80 | printf("%d\n", DP(n - 1, sy, 0));
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
214 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Runtime error |
190 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Runtime error |
192 ms |
524288 KB |
Execution killed with signal 9 |
4 |
Runtime error |
206 ms |
524288 KB |
Execution killed with signal 9 |
5 |
Runtime error |
193 ms |
524288 KB |
Execution killed with signal 9 |
6 |
Runtime error |
212 ms |
524288 KB |
Execution killed with signal 9 |
7 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
8 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
9 |
Runtime error |
197 ms |
524288 KB |
Execution killed with signal 9 |
10 |
Runtime error |
198 ms |
524288 KB |
Execution killed with signal 9 |
11 |
Runtime error |
191 ms |
524288 KB |
Execution killed with signal 9 |
12 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
13 |
Runtime error |
189 ms |
524288 KB |
Execution killed with signal 9 |
14 |
Runtime error |
199 ms |
524288 KB |
Execution killed with signal 9 |
15 |
Runtime error |
201 ms |
524288 KB |
Execution killed with signal 9 |
16 |
Runtime error |
191 ms |
524288 KB |
Execution killed with signal 9 |
17 |
Runtime error |
197 ms |
524288 KB |
Execution killed with signal 9 |
18 |
Runtime error |
229 ms |
524288 KB |
Execution killed with signal 9 |
19 |
Runtime error |
185 ms |
524288 KB |
Execution killed with signal 9 |
20 |
Runtime error |
182 ms |
524288 KB |
Execution killed with signal 9 |