Submission #81416

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
81416	2018-10-24T14:45:54 Z	luckyboy	Retro (COCI17_retro)	C++14	100 / 100	444 ms	243940 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	201 ms	235896 KB	Output is correct
2	Correct	216 ms	235904 KB	Output is correct
3	Correct	193 ms	235944 KB	Output is correct
4	Correct	189 ms	236028 KB	Output is correct
5	Correct	191 ms	236028 KB	Output is correct
6	Correct	196 ms	236292 KB	Output is correct
7	Correct	199 ms	236312 KB	Output is correct
8	Correct	197 ms	236720 KB	Output is correct
9	Correct	189 ms	236720 KB	Output is correct
10	Correct	206 ms	236720 KB	Output is correct
11	Correct	364 ms	238740 KB	Output is correct
12	Correct	337 ms	238740 KB	Output is correct
13	Correct	284 ms	239372 KB	Output is correct
14	Correct	271 ms	239372 KB	Output is correct
15	Correct	444 ms	243940 KB	Output is correct
16	Correct	387 ms	243940 KB	Output is correct
17	Correct	390 ms	243940 KB	Output is correct
18	Correct	342 ms	243940 KB	Output is correct
19	Correct	403 ms	243940 KB	Output is correct
20	Correct	397 ms	243940 KB	Output is correct