답안 #81410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81410	2018-10-24T14:41:57 Z	luckyboy	Retro (COCI17_retro)	C++14	0 / 100	451 ms	525312 KB

retro

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

ll n,m,dp[N][N][N+5];
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.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	384 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Runtime error	413 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	438 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Runtime error	402 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Runtime error	451 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	391 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	441 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	392 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	408 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	404 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	430 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	367 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	388 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	425 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	411 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Runtime error	416 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	421 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	404 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	410 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	409 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)