Submission #39315

#	Time	Username	Problem	Language	Result	Execution time	Memory
39315		Mamnoon_Siam	Retro (COCI17_retro)	C++14	40 / 100	366 ms	110768 KiB

retro

#include <bits/stdc++.h>
using namespace std;
 
#define fasten(v) v.reserve(v.size())
#define wait() system("pause")
#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define read(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) v.begin(), v.end()
#define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL)
#define printBinary(n) cout << #n << " = " << bitset<64>(n) << endl
#define min_pq priority_queue<int, vector<int>, greater<int> >
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define cin(n) scanf("%d", &n)
 
template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); }

typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef pair<double, double> pdd;

#define ceil(num,d) 		( (int)(num/d) + (num%d>0 ? 1 : 0) )
#define block_no(idx) 		( ceil(idx, BLOCK_SIZE) )
#define block_starting(idx) ( ((block_no(idx)-1) * BLOCK_SIZE) +1 )
#define block_ending(idx) 	( min(n, block_no(idx)*BLOCK_SIZE) )
#define block_ranking(idx) 	( (idx % BLOCK_SIZE == 0) ? BLOCK_SIZE : idx % BLOCK_SIZE )

#define mirko 'M'
#define val(ch) (ch == mirko or ch == '.' ? 0 : (ch == '(' ? 1 : -1))
#define bomb '*'
#define inf 1e9

const int maxn = 303;

char s[maxn][maxn];
int n, m, dp[maxn][maxn][maxn];

int get(int x, int y, int open) {
	if(x == 0) return open == 0 ? 0 : -inf;
	if(s[x][y] == bomb) return open == 0 ? 0 : -inf;
	if(open + val(s[x][y]) < 0) return -inf;
	if(dp[x][y][open] != -1) return dp[x][y][open];
	int &ret = dp[x][y][open];
	ret = s[x][y] == '.' or s[x][y] == mirko ? 0 : 1 ; int opt = -inf;
	open += val(s[x][y]);
	if(y>1) { /// left
		int temp = get(x-1, y-1, open);
		if(temp != -inf) opt = max(opt, temp);
	}
	{ /// upper
		int temp = get(x-1, y, open);
		if(temp != -inf) opt = max(opt, temp);
	}
	if(y<m) { // right
		int temp = get(x-1, y+1, open);
		if(temp != -inf) opt = max(opt, temp);
	}
	if(opt == -inf) ret = -inf;
	else ret += opt;
	return ret;
}

int main () {
	//read("input.in");
	MEMSET(dp, -1);
	cin(n), cin(m);
	for(int i=1; i<=n; i++) {
		scanf("%s", s[i]+1);
	}
	int sx = n, sy;
	for(int i=1; i<=m; i++) {
		if(s[n][i] == mirko) {
			sy = i; break;
		}
	}
	cout<<get(sx, sy, 0)<<endl;
	string str(get(sx, sy, 0), '(');
	cout<<str<<endl;
	return 0;
}

Compilation message (stderr)

retro.cpp: In function 'int main()':
retro.cpp:73:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  cin(n), cin(m);
                ^
retro.cpp:73:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
retro.cpp:75:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s[i]+1);
                      ^
retro.cpp:77:14: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int sx = n, sy;
              ^

• Subtask 1: 40 / 100