답안 #36761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36761	2017-12-14T13:05:04 Z	kjain_1810	Retro (COCI17_retro)	C++14	36 / 100	386 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

36.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	3 ms	113300 KB	Partially correct
2	Partially correct	6 ms	113300 KB	Partially correct
3	Partially correct	13 ms	113300 KB	Partially correct
4	Partially correct	13 ms	113300 KB	Partially correct
5	Partially correct	3 ms	113300 KB	Partially correct
6	Partially correct	6 ms	113300 KB	Partially correct
7	Partially correct	9 ms	113300 KB	Partially correct
8	Partially correct	13 ms	113300 KB	Partially correct
9	Incorrect	6 ms	113300 KB	Unexpected end of file - token expected
10	Partially correct	13 ms	113300 KB	Partially correct
11	Partially correct	329 ms	113300 KB	Partially correct
12	Partially correct	226 ms	113300 KB	Partially correct
13	Partially correct	153 ms	113300 KB	Partially correct
14	Incorrect	109 ms	113300 KB	Unexpected end of file - token expected
15	Partially correct	386 ms	113300 KB	Partially correct
16	Partially correct	289 ms	113300 KB	Partially correct
17	Partially correct	376 ms	113300 KB	Partially correct
18	Partially correct	223 ms	113300 KB	Partially correct
19	Partially correct	309 ms	113300 KB	Partially correct
20	Partially correct	316 ms	113300 KB	Partially correct