oj.uz

Submission #236168

# Submission time Handle Problem Language Result Execution time Memory
236168 2020-05-31T10:38:14 Z topovik Retro (COCI17_retro) C++14
70 / 100
 371 ms 251128 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39424 KB Output is correct
2 Correct 31 ms 39424 KB Output is correct
3 Correct 28 ms 39520 KB Output is correct
4 Correct 29 ms 39424 KB Output is correct
5 Correct 37 ms 39424 KB Output is correct
6 Correct 93 ms 54780 KB Output is correct
7 Correct 136 ms 66168 KB Output is correct
8 Correct 72 ms 51064 KB Output is correct
9 Correct 131 ms 68984 KB Output is correct
10 Correct 181 ms 80376 KB Output is correct
11 Partially correct 349 ms 237560 KB Partially correct
12 Partially correct 307 ms 237560 KB Partially correct
13 Partially correct 161 ms 127612 KB Partially correct
14 Partially correct 152 ms 127384 KB Partially correct
15 Partially correct 351 ms 250496 KB Partially correct
16 Partially correct 344 ms 250360 KB Partially correct
17 Partially correct 305 ms 218360 KB Partially correct
18 Partially correct 289 ms 218232 KB Partially correct
19 Partially correct 371 ms 251128 KB Partially correct
20 Partially correct 345 ms 251064 KB Partially correct