oj.uz

Submission #36761

# Submission time Handle Problem Language Result Execution time Memory
36761 2017-12-14T13:05:04 Z kjain_1810 Retro (COCI17_retro) C++14
36 / 100
 386 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
36.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 113300 KB Partially correct
2 Partially correct 6 ms 113300 KB Partially correct
3 Partially correct 13 ms 113300 KB Partially correct
4 Partially correct 13 ms 113300 KB Partially correct
5 Partially correct 3 ms 113300 KB Partially correct
6 Partially correct 6 ms 113300 KB Partially correct
7 Partially correct 9 ms 113300 KB Partially correct
8 Partially correct 13 ms 113300 KB Partially correct
9 Incorrect 6 ms 113300 KB Unexpected end of file - token expected
10 Partially correct 13 ms 113300 KB Partially correct
11 Partially correct 329 ms 113300 KB Partially correct
12 Partially correct 226 ms 113300 KB Partially correct
13 Partially correct 153 ms 113300 KB Partially correct
14 Incorrect 109 ms 113300 KB Unexpected end of file - token expected
15 Partially correct 386 ms 113300 KB Partially correct
16 Partially correct 289 ms 113300 KB Partially correct
17 Partially correct 376 ms 113300 KB Partially correct
18 Partially correct 223 ms 113300 KB Partially correct
19 Partially correct 309 ms 113300 KB Partially correct
20 Partially correct 316 ms 113300 KB Partially correct