Submission #635304

#	Time	Username	Problem	Language	Result	Execution time	Memory
635304		racsosabe	Retro (COCI17_retro)	C++14	70 / 100	251 ms	142600 KiB

retro

#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[105][105][105];

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("(");
	return 0;
}

Compilation message (stderr)

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: 70 / 100