oj.uz

Submission #39315

# Submission time Handle Problem Language Result Execution time Memory
39315 2018-01-11T07:17:26 Z Mamnoon_Siam Retro (COCI17_retro) C++14
40 / 100
 366 ms 110768 KB 
#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

# Verdict Execution time Memory 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