답안 #39315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39315	2018-01-11T07:17:26 Z	Mamnoon_Siam	Retro (COCI17_retro)	C++14	40 / 100	366 ms	110768 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	110768 KB	Partially correct
2	Partially correct	3 ms	110768 KB	Partially correct
3	Partially correct	16 ms	110768 KB	Partially correct
4	Partially correct	16 ms	110768 KB	Partially correct
5	Partially correct	13 ms	110768 KB	Partially correct
6	Partially correct	6 ms	110768 KB	Partially correct
7	Partially correct	13 ms	110768 KB	Partially correct
8	Partially correct	6 ms	110768 KB	Partially correct
9	Partially correct	16 ms	110768 KB	Partially correct
10	Partially correct	16 ms	110768 KB	Partially correct
11	Partially correct	209 ms	110768 KB	Partially correct
12	Partially correct	183 ms	110768 KB	Partially correct
13	Partially correct	86 ms	110768 KB	Partially correct
14	Partially correct	86 ms	110768 KB	Partially correct
15	Partially correct	366 ms	110768 KB	Partially correct
16	Partially correct	286 ms	110768 KB	Partially correct
17	Partially correct	316 ms	110768 KB	Partially correct
18	Partially correct	186 ms	110768 KB	Partially correct
19	Partially correct	276 ms	110768 KB	Partially correct
20	Partially correct	189 ms	110768 KB	Partially correct