Submission #635297

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
635297	2022-08-26T00:06:34 Z	racsosabe	Retro (COCI17_retro)	C++14	50 / 100	52 ms	73956 KB

retro

#include<bits/stdc++.h>
using namespace::std;

const int N = 100 + 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];

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);
	printf("%s\n", get_ans(n - 1, sy, 0).c_str());
	return 0;
}

Compilation message

retro.cpp: In function 'std::string get_ans(int, int, int)':
retro.cpp:40:6: warning: variable 'best' set but not used [-Wunused-but-set-variable]
   40 |  int best;
      |      ^~~~
retro.cpp: In function 'int main()':
retro.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
retro.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%s", s[i]);
      |   ~~~~~^~~~~~~~~~~~
retro.cpp:78:8: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |  printf("%d\n", DP(n - 1, sy, 0));
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	37716 KB	Output is correct
2	Correct	17 ms	37728 KB	Output is correct
3	Correct	17 ms	37732 KB	Output is correct
4	Correct	18 ms	37740 KB	Output is correct
5	Correct	20 ms	37728 KB	Output is correct
6	Correct	19 ms	39264 KB	Output is correct
7	Correct	20 ms	39200 KB	Output is correct
8	Correct	20 ms	39252 KB	Output is correct
9	Correct	22 ms	40344 KB	Output is correct
10	Correct	23 ms	40952 KB	Output is correct
11	Runtime error	46 ms	73832 KB	Execution killed with signal 11
12	Runtime error	46 ms	73932 KB	Execution killed with signal 11
13	Runtime error	46 ms	73928 KB	Execution killed with signal 11
14	Runtime error	46 ms	73956 KB	Execution killed with signal 11
15	Runtime error	48 ms	73932 KB	Execution killed with signal 11
16	Runtime error	45 ms	73880 KB	Execution killed with signal 11
17	Runtime error	44 ms	73840 KB	Execution killed with signal 11
18	Runtime error	44 ms	73932 KB	Execution killed with signal 11
19	Runtime error	52 ms	73884 KB	Execution killed with signal 11
20	Runtime error	48 ms	73828 KB	Execution killed with signal 11