oj.uz

Submission #635304

# Submission time Handle Problem Language Result Execution time Memory
635304 2022-08-26T00:25:07 Z racsosabe Retro (COCI17_retro) C++14
70 / 100
 251 ms 142600 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[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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64308 KB Output is correct
2 Correct 29 ms 64388 KB Output is correct
3 Correct 33 ms 64468 KB Output is correct
4 Correct 28 ms 64512 KB Output is correct
5 Correct 27 ms 64508 KB Output is correct
6 Correct 30 ms 68576 KB Output is correct
7 Correct 31 ms 68272 KB Output is correct
8 Correct 34 ms 68172 KB Output is correct
9 Correct 34 ms 71528 KB Output is correct
10 Correct 44 ms 73224 KB Output is correct
11 Partially correct 211 ms 134472 KB Partially correct
12 Partially correct 163 ms 129176 KB Partially correct
13 Partially correct 101 ms 103240 KB Partially correct
14 Partially correct 114 ms 101972 KB Partially correct
15 Partially correct 251 ms 139764 KB Partially correct
16 Partially correct 202 ms 133500 KB Partially correct
17 Partially correct 231 ms 134280 KB Partially correct
18 Partially correct 172 ms 129296 KB Partially correct
19 Partially correct 249 ms 142600 KB Partially correct
20 Partially correct 243 ms 136964 KB Partially correct