Submission #36788

#	Time	Username	Problem	Language	Result	Execution time	Memory
36788		kjain_1810	Retro (COCI17_retro)	C++14	25 / 100	500 ms	334596 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=1e5+5;
typedef long long ll;
int r, s;
int dp[305][305][305];
pair<int,int> backtrack[305][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(dp[i][j][numopen]!=-1)
		return dp[i][j][numopen];
	if(str[i][j]=='M' || str[i][j]=='.')
	{
		int ans=solve(i-1, j, numopen);
		backtrack[i][j][numopen]={0,0};
		if(j>1)
		{
			int tmp=solve(i-1, j-1, numopen);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j][numopen]={-1, 0};
			}
		}
		if(j<s)
		{
			int tmp=solve(i-1, j+1, numopen);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j][numopen]={1, 0};
			}
		}
		return dp[i][j][numopen]=ans;
	}
	if(str[i][j]=='(')
	{
		int ans=solve(i-1, j, numopen+1);
		backtrack[i][j][numopen]={0, 1};
		if(j>1)
		{
			int tmp=solve(i-1, j-1, numopen+1);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j][numopen]={-1, 1};
			}
		}
		if(j<s)
		{
			int tmp=solve(i-1, j+1, numopen+1);
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j][numopen]={1, 1};
			}
		}
		return dp[i][j][numopen]=ans;
	}
	else if(str[i][j]==')')
	{
		int ans=solve(i-1, j, numopen-1)+1;
		backtrack[i][j][numopen]={0,-1};
		if(j>1)
		{
			int tmp=solve(i-1, j-1, numopen-1)+1;
			if(tmp>ans)
			{
				ans=tmp;
				backtrack[i][j][numopen]={-1, -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][numopen]={1, -1};
			}
			// ans=max(ans, solve(i-1, j+1, numopen-1)+1);
		}
		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, num=0;
	while(1)
	{	
		if(str[i][j]=='*' || i==0 || num<0)
			break;
		if(str[i][j]=='(' || str[i][j]==')')
			printf("%c", str[i][j]);
		j+=backtrack[i][j][num].f;
		num+=backtrack[i][j][num].s;
		i--;
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

retro.cpp: In function 'int solve(int, int, int)':
retro.cpp:102:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
retro.cpp: In function 'int main()':
retro.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  ind(r);
        ^
retro.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  ind(s);
        ^
retro.cpp:123:14: warning: 'startj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(str[i][j]=='*' || i==0 || num<0)
              ^
retro.cpp:119:24: warning: 'starti' may be used uninitialized in this function [-Wmaybe-uninitialized]
  printf("%d\n", 2*solve(starti, startj, 0));
                        ^

• Subtask 1: 25 / 100