Submission #236168

#	Time	Username	Problem	Language	Result	Execution time	Memory
236168		topovik	Retro (COCI17_retro)	C++14	70 / 100	371 ms	251128 KiB

retro

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define f first
#define s second

const int N = 300;

pair<int,string> dp1[100][100][100];

string a[N];

int dp[300][300][301];
int pred[300][300][301];
int n,m;
int pos=0;



void Case1()
{
    for (int i=0; i<n; i++)
    for (int j=0; j<m; j++)
      for (int c=0; c<300; c++) dp[i][j][c]=-1e9;
  dp[0][pos][0]=0;
  for (int i=0; i<n-1; i++)
  {
      for (int j=0; j<m; j++)
        if (a[i][j]!='*')
        for (int c=0; c<300; c++)
        {
            for (int c1=-1; c1<=1; c1++)
            {
                int j1=j+c1;
                if (j1>-1 && j1<m)
                {
                    if ((a[i+1][j1]!='(' && a[i+1][j1]!=')') && dp[i+1][j1][c]<dp[i][j][c]) dp[i+1][j1][c]=dp[i][j][c],pred[i+1][j1][c]=-c1;
                    if (a[i+1][j1]=='(' && dp[i+1][j1][c+1]<dp[i][j][c]+1) dp[i+1][j1][c+1]=dp[i][j][c]+1,pred[i+1][j1][c+1]=-c1;
                    if (a[i+1][j1]==')' && c>0 && dp[i+1][j1][c-1]<dp[i][j][c]+1) dp[i+1][j1][c-1]=dp[i][j][c]+1,pred[i+1][j1][c-1]=-c1;
                }
            }
        }
  }
  int mx=0,x=0,y=0;
  for (int i=0; i<n; i++)
    for (int j=0; j<m; j++)
        if (a[i][j]=='*' || i==n-1)
          if (dp[i][j][0]>mx) mx=max(mx,dp[i][j][0]),x=i,y=j;
  cout<<mx<<endl;
  string s;
  int bal=0;
  while (x>0)
  {
      int upd=0;
      if (a[x][y]=='(' || a[x][y]==')')
      {
          s+=a[x][y];
          if (a[x][y]=='(') upd--;
          else              upd++;
      }
      y+=pred[x][y][bal];
      bal+=upd;
      x--;
  }
  reverse(s.begin(),s.end());
  cout<<s;
}

void Case2()
{
    for (int i=0; i<n; i++)
    for (int j=0; j<m; j++)
      for (int c=0; c<100; c++) dp1[i][j][c]={1e9,""};
  dp1[0][pos][0]={0,""};
  for (int i=0; i<n-1; i++)
  {
      for (int j=0; j<m; j++)
        if (a[i][j]!='*')
        for (int c=0; c<100; c++)
        {
            for (int c1=-1; c1<=1; c1++)
            {
                int j1=j+c1;
                if (j1>-1 && j1<m)
                {
                    if (a[i+1][j1]!='(' && a[i+1][j1]!=')') dp1[i+1][j1][c]=min(dp1[i+1][j1][c],dp1[i][j][c]);
                    if (a[i+1][j1]=='(' ) dp1[i+1][j1][c+1]=min(dp1[i+1][j1][c+1],{dp1[i][j][c].f-1,dp1[i][j][c].s+"("});
                    if (a[i+1][j1]==')' && c>0) dp1[i+1][j1][c-1]=min(dp1[i+1][j1][c-1],{dp1[i][j][c].f-1,dp1[i][j][c].s+")"});
                }
            }
        }
  }
  pair<int,string> mx={0,""};
  for (int i=0; i<n; i++)
    for (int j=0; j<m; j++)
      if (a[i][j]=='*' || i==n-1) mx=min(mx,dp1[i][j][0]);
  cout<<-mx.f<<"\n"<<mx.s;
}
int main()
{
  cin>>n>>m;
  for (int i=0; i<n; i++) cin>>a[i];
  reverse(a,a+n);
  for (int j=0; j<m; j++)
    if (a[0][j]=='M') pos=j;
  if (n>100) Case1();
  else       Case2();
}

• Subtask 1: 70 / 100