| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 36785 | kjain_1810 | Retro (COCI17_retro) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ind(a) scanf("%d", &a)
#define inlld(a) scanf("%lld", &a)
#define pb push_back
#define f first
#define s second
using namespace std;
const int N=1e5+5;
typedef long long ll;
int r, s;
int dp[305][305][305];
pair<int,int> backtrack[305][305];
char str[305][305][305];
int solve(int i, int j, int numopen)
{
if(i==0 && numopen==0)
return 0;
else if(i==0)
return -1e9;
if(numopen<0)
return -1e9;
if(str[i][j]=='*' && numopen==0)
return 0;
else if(str[i][j]=='*')
return -1e9;
if(dp[i][j][numopen]!=-1)
return dp[i][j][numopen];
if(str[i][j]=='M' || str[i][j]=='.')
{
int ans=solve(i-1, j, numopen);
backtrack[i][j]={0,0};
if(j>1)
{
int tmp=solve(i-1, j-1, numopen);
if(tmp>ans)
{
ans=tmp;
backtrack[i][j]={-1, 0};
}
}
if(j<s)
{
int tmp=solve(i-1, j+1, numopen);
if(tmp>ans)
{
ans=tmp;
backtrack[i][j]={1, 0};
}
}
return dp[i][j][numopen]=ans;
}
if(str[i][j]=='(')
{
int ans=solve(i-1, j, numopen+1);
backtrack[i][j]={0, 1};
if(j>1)
{
int tmp=solve(i-1, j-1, numopen+1);
if(tmp>ans)
{
ans=tmp;
backtrack[i][j]={-1, 1};
}
}
if(j<s)
{
int tmp=solve(i-1, j+1, numopen+1);
if(tmp>ans)
{
ans=tmp;
backtrack[i][j]={1, 1};
}
}
return dp[i][j][numopen]=ans;
}
else if(str[i][j]==')')
{
int ans=solve(i-1, j, numopen-1)+1;
backtrack[i][j]=0;
if(j>1)
{
int tmp=solve(i-1, j-1, numopen-1)+1;
if(tmp>ans)
{
ans=tmp;
backtrack[i][j]={-1, -1};
}
// ans=max(ans, solve(i-1, j-1, numopen-1)+1);
}
if(j<s)
{
int tmp=solve(i-1, j+1, numopen-1)+1;
if(tmp>ans)
{
ans=tmp;
backtrack[i][j]={1, -1};
}
// ans=max(ans, solve(i-1, j+1, numopen-1)+1);
}
return dp[i][j][numopen]=ans;
}
}
int main()
{
ind(r);
ind(s);
for(int a=1; a<=r; a++)
for(int b=1; b<=s; b++)
cin>>str[a][b];
memset(dp, -1, sizeof(dp));
int starti, startj;
for(int a=1; a<=s; a++)
if(str[r][a]=='M')
{
starti=r;
startj=a;
break;
}
printf("%d\n", 2*solve(starti, startj, 0));
int i=r, j=startj, num=0;
while(1)
{
if(str[i][j]=='*' || i==0 || num<0)
break;
if(str[i][j]=='(' || str[i][j]==')')
printf("%c", str[i][j]);
j+=backtrack[i][j].f;
num+=backtrack[i][j].s;
i--;
}
printf("\n");
return 0;
}