oj.uz

Submission #635303

# Submission time Handle Problem Language Result Execution time Memory
635303 2022-08-26T00:24:39 Z racsosabe Retro (COCI17_retro) C++14
50 / 100
 271 ms 142724 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("A");
	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 27 ms 64272 KB Output is correct
2 Correct 28 ms 64368 KB Output is correct
3 Correct 27 ms 64432 KB Output is correct
4 Correct 28 ms 64480 KB Output is correct
5 Correct 29 ms 64556 KB Output is correct
6 Correct 35 ms 68568 KB Output is correct
7 Correct 31 ms 68308 KB Output is correct
8 Correct 31 ms 68136 KB Output is correct
9 Correct 38 ms 71548 KB Output is correct
10 Correct 36 ms 73256 KB Output is correct
11 Incorrect 212 ms 134360 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
12 Incorrect 171 ms 129272 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
13 Incorrect 112 ms 103348 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
14 Incorrect 101 ms 101920 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
15 Incorrect 271 ms 139692 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
16 Incorrect 228 ms 133580 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
17 Incorrect 205 ms 134232 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
18 Incorrect 172 ms 129356 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
19 Incorrect 250 ms 142724 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"
20 Incorrect 207 ms 137148 KB Token "A" doesn't correspond to pattern "[\(\)]{1,100000}"