답안 #81416

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81416 2018-10-24T14:45:54 Z luckyboy Retro (COCI17_retro) C++14
100 / 100
444 ms 243940 KB
#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";
}
# 결과 실행 시간 메모리 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