Submission #236137

#	Time	Username	Problem	Language	Result	Execution time	Memory
236137		topovik	Retro (COCI17_retro)	C++14	46 / 100	384 ms	212040 KiB

retro

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

int dp[300][300][301];
int pred[300][300][301];

int main()
{
  int n,m;
  cin>>n>>m;
  string a[n];
  for (int i=0; i<n; i++) cin>>a[i];
  reverse(a,a+n);
  int pos=0;
  for (int j=0; j<m; j++)
    if (a[0][j]=='M') pos=j;
  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;
}

• Subtask 1: 46 / 100