Submission #36789

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36789	2017-12-14T15:16:48 Z	kjain_1810	Retro (COCI17_retro)	C++14	39 / 100	500 ms	334596 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=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]);
		pair<int, int>x=backtrack[i][j][num];
		j+=x.f;
		num+=x.s;
		i--;
	}
	printf("\n");
	return 0;
}

Compilation message

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

39.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	334596 KB	Partially correct
2	Correct	9 ms	334596 KB	Output is correct
3	Partially correct	6 ms	334596 KB	Partially correct
4	Partially correct	6 ms	334596 KB	Partially correct
5	Partially correct	16 ms	334596 KB	Partially correct
6	Partially correct	13 ms	334596 KB	Partially correct
7	Correct	6 ms	334596 KB	Output is correct
8	Partially correct	9 ms	334596 KB	Partially correct
9	Partially correct	26 ms	334596 KB	Partially correct
10	Correct	16 ms	334596 KB	Output is correct
11	Execution timed out	500 ms	334596 KB	Execution timed out
12	Partially correct	486 ms	334596 KB	Partially correct
13	Partially correct	323 ms	334596 KB	Partially correct
14	Partially correct	249 ms	334596 KB	Partially correct
15	Execution timed out	500 ms	334596 KB	Execution timed out
16	Partially correct	483 ms	334596 KB	Partially correct
17	Execution timed out	500 ms	334596 KB	Execution timed out
18	Partially correct	423 ms	334596 KB	Partially correct
19	Execution timed out	500 ms	334596 KB	Execution timed out
20	Execution timed out	500 ms	334596 KB	Execution timed out