Submission #81413

#	Time	Username	Problem	Language	Result	Execution time	Memory
81413		luckyboy	Retro (COCI17_retro)	C++14	0 / 100	444 ms	525312 KiB

retro

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define N ((ll)301)
#define INF ((ll)1e5)

ll n,m,dp[N][N][N];
string s[N];
ll strt;
string out[N][N][N];
bool ok[N][N][N];

void solve(ll i,ll j,ll k)
{
	if(i==0 || j==0 || j==m+1 || s[i][j]=='*')
		ok[i][j][k]=1;
	if(ok[i][j][k])return ;
	if(s[i][j]=='.' || s[i][j]=='M')
	{
		for(int p=j-1;p<=j+1;p++)
			if(dp[i-1][p][k]==dp[i][j][k])
			{
				solve(i-1,p,k);
				if(!ok[i][j][k] || out[i][j][k]>out[i-1][p][k])
					ok[i][j][k]=1,out[i][j][k]=out[i-1][p][k];
			}
	//	cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<"\n";
	//	cout<<out[i][j][k]<<"\n";
		return ;
	}
	if(s[i][j]=='(')
	{
		for(int p=j-1;p<=j+1;p++)
			if(dp[i-1][p][k+1]==dp[i][j][k])
			{
				solve(i-1,p,k+1);
				if(!ok[i][j][k] || out[i][j][k]>out[i-1][p][k+1])
					ok[i][j][k]=1,out[i][j][k]=out[i-1][p][k+1];
			}
		out[i][j][k]='('+out[i][j][k];
	//	cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<"\n";
	//	cout<<out[i][j][k]<<"\n";
		return ;
	}
	for(int p=j-1;p<=j+1;p++)
		if(dp[i-1][p][k-1]+1==dp[i][j][k])
		{
			solve(i-1,p,k-1);
			if(!ok[i][j][k] || out[i][j][k]>out[i-1][p][k-1])
				ok[i][j][k]=1,out[i][j][k]=out[i-1][p][k-1];
		}
	out[i][j][k]=')'+out[i][j][k];
//	cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<"\n";
//	cout<<out[i][j][k]<<"\n";
}

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		for(int j=1;j<N;j++)
			dp[0][i][j]=-INF;
	for(int i=1;i<=n;i++)
		for(int j=0;j<N;j++)
			dp[i][0][j]=dp[i][m+1][j]=-INF;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];s[i]='.'+s[i];
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]=='M')strt=j;
			for(int k=0;k<N;k++)
			{
				if(s[i][j]=='*')
				{
					if(k>0)dp[i][j][k]=-INF;
					continue;
				}
				if(s[i][j]=='.' || s[i][j]=='M')
				{
					dp[i][j][k]=max({dp[i-1][j][k],dp[i-1][j-1][k],dp[i-1][j+1][k]});
					continue;
				}
				if(s[i][j]=='(')
				{
					dp[i][j][k]=max({dp[i-1][j][k+1],dp[i-1][j-1][k+1],dp[i-1][j+1][k+1]});
					continue;
				}
				if(k>0)
					dp[i][j][k]=1+max({dp[i-1][j][k-1],dp[i-1][j-1][k-1],dp[i-1][j+1][k-1]});
				else
					dp[i][j][k]=-INF;
			}
		}
	}
	cout<<dp[n][strt][0]*2<<"\n";
	solve(n,strt,0);
	cout<<out[n][strt][0]<<"\n";
	return 0;
}

• Subtask 1: 0 / 100