oj.uz

Submission #81413

# Submission time Handle Problem Language Result Execution time Memory
81413 2018-10-24T14:44:06 Z luckyboy Retro (COCI17_retro) C++14
0 / 100
 444 ms 525312 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 406 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 367 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 410 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 368 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 360 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 358 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 356 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 413 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 380 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 410 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 378 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 419 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 387 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 412 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 376 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 404 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 444 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 374 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 388 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 422 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)