답안 #36762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36762	2017-12-14T13:10:32 Z	kjain_1810	Retro (COCI17_retro)	C++14	43 / 100	409 ms	113300 KB

retro

#include<bits/stdc++.h>
#define ind(a) scanf("%d", &a)
#define inlld(a) scanf("%lld", &a)
#define pb push_back
#define f first
#define s second
using namespace std;
const int N=5e5+5;
typedef long long ll;
int r, s;
int dp[305][305][305];
int backtrack[305][305];
char str[305][305];
int solve(int i, int j, int numopen)
{
	if(i==0 && numopen==0)
		return 0;
	else if(i==0)
		return -1e9;
	if(numopen<0)
		return -1e9;
	if(str[i][j]=='*' && numopen==0)
		return 0;
	else if(str[i][j]=='*')
		return -1e9;
	if(str[i][j]=='M')
	{
		int ans=solve(i-1, j, numopen);
		backtrack[i][j]=0;
		if(j>1)
		{
			int tmp=solve(i-1, j-1, numopen);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j]=-1;
			}
		}
		if(j<s)
		{
			int tmp=solve(i-1, j+1, numopen);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j]=1;
			}
			// ans=max(ans, solve(i-1, j+1, numopen));
		}
		return ans;
	}
	if(dp[i][j][numopen]!=-1)
		return dp[i][j][numopen];
	if(str[i][j]=='(')
	{
		int ans=solve(i-1, j, numopen+1);
		backtrack[i][j]=0;
		if(j>1)
		{
			int tmp=solve(i-1, j-1, numopen+1);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j]=-1;
			}
			// ans=max(ans, solve(i-1, j-1, numopen+1));
		}
		if(j<s)
		{
			int tmp=solve(i-1, j+1, numopen+1);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j]=1;
			}
			// ans=max(ans, solve(i-1, j+1, numopen+1));
		}
		return dp[i][j][numopen]=ans;
	}
	else if(str[i][j]==')')
	{
		int ans=solve(i-1, j, numopen-1)+1;
		backtrack[i][j]=0;
		if(j>1)
		{
			int tmp=solve(i-1, j-1, numopen-1)+1;
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j]=-1;
			}
			// ans=max(ans, solve(i-1, j-1, numopen-1)+1);
		}
		if(j<s)
		{
			int tmp=solve(i-1, j+1, numopen-1)+1;
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j]=1;
			}
			// ans=max(ans, solve(i-1, j+1, numopen-1)+1);
		}
		return dp[i][j][numopen]=ans;
	}
	else
	{
		int ans=solve(i-1, j, numopen);
		backtrack[i][j]=0;
		if(j>1)
		{
			int tmp=solve(i-1, j-1, numopen);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j]=-1;
			}
			// ans=max(ans, solve(i-1, j-1, numopen));
		}
		if(j<s)
		{
			int tmp=solve(i-1, j+1, numopen);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j]=1;
			}
			// ans=max(ans, solve(i-1, j+1, numopen));
		}
		return dp[i][j][numopen]=ans;
	}
}
int main()
{
	ind(r);
	ind(s);
	for(int a=1; a<=r; a++)
		for(int b=1; b<=s; b++)
			cin>>str[a][b];
	memset(dp, -1, sizeof(dp));
	int starti, startj;
	for(int a=1; a<=s; a++)
		if(str[r][a]=='M')
		{
			starti=r;
			startj=a;
			break;
		}
	printf("%d\n", 2*solve(starti, startj, 0));
	int i=r, j=startj;
	while(1)
	{	
		if(str[i][j]=='*')
			break;
		if(str[i][j]=='(' || str[i][j]==')')
			printf("%c", str[i][j]);
		if(backtrack[i][j]==-1)
			j--;
		else if(backtrack[i][j]==1)
			j++;
		i--;
		if(i==0)
			break;
	}
	printf("\n");
	return 0;
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  ind(r);
        ^
retro.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  ind(s);
        ^
retro.cpp:140:14: warning: 'startj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int starti, startj;
              ^
retro.cpp:140:6: warning: 'starti' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int starti, startj;
      ^

Subtask #1

43.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	113300 KB	Partially correct
2	Correct	13 ms	113300 KB	Output is correct
3	Partially correct	13 ms	113300 KB	Partially correct
4	Partially correct	16 ms	113300 KB	Partially correct
5	Partially correct	13 ms	113300 KB	Partially correct
6	Partially correct	6 ms	113300 KB	Partially correct
7	Partially correct	13 ms	113300 KB	Partially correct
8	Partially correct	3 ms	113300 KB	Partially correct
9	Partially correct	9 ms	113300 KB	Partially correct
10	Partially correct	19 ms	113300 KB	Partially correct
11	Partially correct	273 ms	113300 KB	Partially correct
12	Partially correct	273 ms	113300 KB	Partially correct
13	Partially correct	109 ms	113300 KB	Partially correct
14	Partially correct	113 ms	113300 KB	Partially correct
15	Partially correct	409 ms	113300 KB	Partially correct
16	Partially correct	313 ms	113300 KB	Partially correct
17	Partially correct	316 ms	113300 KB	Partially correct
18	Partially correct	256 ms	113300 KB	Partially correct
19	Partially correct	406 ms	113300 KB	Partially correct
20	Partially correct	299 ms	113300 KB	Partially correct