oj.uz

Submission #36762

# Submission time Handle Problem Language Result Execution time Memory
36762 2017-12-14T13:10:32 Z kjain_1810 Retro (COCI17_retro) C++14
43 / 100
 409 ms 113300 KB 
#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
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 113300 KB Partially correct
2 Correct 13 ms 113300 KB Output is correct
3 Partially correct 13 ms 113300 KB Partially correct
4 Partially correct 16 ms 113300 KB Partially correct
5 Partially correct 13 ms 113300 KB Partially correct
6 Partially correct 6 ms 113300 KB Partially correct
7 Partially correct 13 ms 113300 KB Partially correct
8 Partially correct 3 ms 113300 KB Partially correct
9 Partially correct 9 ms 113300 KB Partially correct
10 Partially correct 19 ms 113300 KB Partially correct
11 Partially correct 273 ms 113300 KB Partially correct
12 Partially correct 273 ms 113300 KB Partially correct
13 Partially correct 109 ms 113300 KB Partially correct
14 Partially correct 113 ms 113300 KB Partially correct
15 Partially correct 409 ms 113300 KB Partially correct
16 Partially correct 313 ms 113300 KB Partially correct
17 Partially correct 316 ms 113300 KB Partially correct
18 Partially correct 256 ms 113300 KB Partially correct
19 Partially correct 406 ms 113300 KB Partially correct
20 Partially correct 299 ms 113300 KB Partially correct