Submission #36788

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36788	2017-12-14T15:15:35 Z	kjain_1810	Retro (COCI17_retro)	C++14	25 / 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]);
		j+=backtrack[i][j][num].f;
		num+=backtrack[i][j][num].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

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	13 ms	334596 KB	Partially correct
2	Correct	6 ms	334596 KB	Output is correct
3	Partially correct	23 ms	334596 KB	Partially correct
4	Partially correct	16 ms	334596 KB	Partially correct
5	Partially correct	13 ms	334596 KB	Partially correct
6	Partially correct	13 ms	334596 KB	Partially correct
7	Partially correct	9 ms	334596 KB	Partially correct
8	Partially correct	6 ms	334596 KB	Partially correct
9	Incorrect	13 ms	334596 KB	Unexpected end of file - token expected
10	Partially correct	23 ms	334596 KB	Partially correct
11	Execution timed out	500 ms	334596 KB	Execution timed out
12	Execution timed out	500 ms	334596 KB	Execution timed out
13	Partially correct	293 ms	334596 KB	Partially correct
14	Partially correct	256 ms	334596 KB	Partially correct
15	Execution timed out	500 ms	334596 KB	Execution timed out
16	Execution timed out	500 ms	334596 KB	Execution timed out
17	Execution timed out	500 ms	334596 KB	Execution timed out
18	Execution timed out	500 ms	334596 KB	Execution timed out
19	Execution timed out	500 ms	334596 KB	Execution timed out
20	Execution timed out	500 ms	334596 KB	Execution timed out