Submission #36761

#	Time	Username	Problem	Language	Result	Execution time	Memory
36761		kjain_1810	Retro (COCI17_retro)	C++14	36 / 100	386 ms	113300 KiB

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 (stderr)

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 / 100