Submission #81416

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

retro

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,j,d[311][311][311],hz,h;
char a[1010][1010];
unordered_map<ll,unordered_map<ll,unordered_map<ll,string> > > s;
bool b[311][311][311];
string hzz;
string rct(ll aa,ll bb,ll cc)
{
//	cout<<aa<<" "<<bb<<" "<<cc<<"\n";
	if(!b[aa][bb][cc])
	{
		b[aa][bb][cc]=1;
		if(a[bb][cc]=='('||a[bb][cc]==')')
			s[aa][bb][cc]=a[bb][cc];
		if(a[bb][cc]=='*'||bb==1)
			return s[aa][bb][cc];
		s[aa][bb][cc]=char(240);
		if(d[aa+(a[bb-1][cc]=='(')-(aa>0&&a[bb-1][cc]==')')][bb-1][cc]+(a[bb-1][cc]!='.')==d[aa][bb][cc])
			s[aa][bb][cc]=rct(aa+(a[bb-1][cc]=='(')-(aa>0&&a[bb-1][cc]==')'),bb-1,cc);
		if(cc>1)
		if(d[aa+(a[bb-1][cc-1]=='(')-(aa>0&&a[bb-1][cc-1]==')')][bb-1][cc-1]+(a[bb-1][cc-1]!='.')==d[aa][bb][cc])
			s[aa][bb][cc]=min(s[aa][bb][cc],rct(aa+(a[bb-1][cc-1]=='(')-(aa>0&&a[bb-1][cc-1]==')'),bb-1,cc-1));
		if(cc<m)
		if(d[aa+(a[bb-1][cc+1]=='(')-(aa>0&&a[bb-1][cc+1]==')')][bb-1][cc+1]+(a[bb-1][cc+1]!='.')==d[aa][bb][cc])
			s[aa][bb][cc]=min(s[aa][bb][cc],rct(aa+(a[bb-1][cc+1]=='(')-(aa>0&&a[bb-1][cc+1]==')'),bb-1,cc+1));
		
		if(a[bb][cc]=='('||a[bb][cc]==')')
			s[aa][bb][cc]=a[bb][cc]+s[aa][bb][cc];
	}
	return s[aa][bb][cc];
}
ll rmt(ll aa,ll bb,ll cc)
{
	//cout<<aa<<" "<<bb<<" "<<cc<<"\n";
	if(a[bb][cc]==')')
		aa--;
	else
	if(a[bb][cc]=='(')
		aa++;
	else
	if(a[bb][cc]=='*')
	{
		if(aa==0)
		{
			d[aa][bb][cc]=-1;
			return -1;
		}
		else
		{
			d[aa][bb][cc]=-10e17;
			return -10e17;
		}
	}
	if(cc<1||cc>m||aa<0)
	{
		if(aa>=0)
			d[aa][bb][cc]=-10e17;
		return -10e17;
	}
	if(bb==1&&aa==0)
	{
		d[aa][bb][cc]=0;
		return 0;
	}
	if(bb==1)
	{
		d[aa][bb][cc]=-10e17;
		return -10e17;
	}
	if(d[aa][bb][cc]==-1)
	{
		d[aa][bb][cc]=(a[bb-1][cc]!='.')+rmt(aa,bb-1,cc);
		if(cc>1)
			d[aa][bb][cc]=max(d[aa][bb][cc],(a[bb-1][cc-1]!='.')+rmt(aa,bb-1,cc-1));
		if(cc<m)
			d[aa][bb][cc]=max(d[aa][bb][cc],(a[bb-1][cc+1]!='.')+rmt(aa,bb-1,cc+1));
	}
	return d[aa][bb][cc];
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			cin>>a[i][j];
	memset(d,-1,sizeof(d));
	for(i=1;i<=m;i++)
		if(a[n][i]=='M')
		{
			hz=rmt(0,n,i);
			h=i;
			cout<<hz<<"\n";
			hzz=rct(0,n,i);
			for(j=hzz.length();j<hz;j++)
				hzz+')';
			cout<<hzz<<"\n";
			return 0;
		}
		
//	cout<<hz<<"\n";
}

• Subtask 1: 100 / 100