oj.uz

Submission #635296

# Submission time Handle Problem Language Result Execution time Memory
635296 2022-08-26T00:06:13 Z racsosabe Retro (COCI17_retro) C++14
20 / 100
 1 ms 852 KB 
#include<bits/stdc++.h>
using namespace::std;

const int N = 15 + 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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 0 ms 596 KB Output isn't correct
6 Runtime error 1 ms 852 KB Execution killed with signal 11
7 Runtime error 1 ms 852 KB Execution killed with signal 11
8 Runtime error 1 ms 852 KB Execution killed with signal 11
9 Runtime error 1 ms 852 KB Execution killed with signal 11
10 Runtime error 1 ms 852 KB Execution killed with signal 11
11 Runtime error 1 ms 852 KB Execution killed with signal 11
12 Runtime error 1 ms 852 KB Execution killed with signal 11
13 Runtime error 1 ms 852 KB Execution killed with signal 11
14 Runtime error 1 ms 852 KB Execution killed with signal 11
15 Runtime error 1 ms 852 KB Execution killed with signal 11
16 Runtime error 1 ms 852 KB Execution killed with signal 11
17 Runtime error 1 ms 852 KB Execution killed with signal 11
18 Runtime error 1 ms 852 KB Execution killed with signal 11
19 Runtime error 1 ms 852 KB Execution killed with signal 11
20 Runtime error 1 ms 852 KB Execution killed with signal 11