oj.uz

Submission #236137

# Submission time Handle Problem Language Result Execution time Memory
236137 2020-05-31T09:19:10 Z topovik Retro (COCI17_retro) C++14
46 / 100
 384 ms 212040 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 512 KB Partially correct
2 Correct 6 ms 1024 KB Output is correct
3 Partially correct 5 ms 768 KB Partially correct
4 Partially correct 6 ms 1280 KB Partially correct
5 Correct 10 ms 3840 KB Output is correct
6 Partially correct 27 ms 11768 KB Partially correct
7 Partially correct 34 ms 17528 KB Partially correct
8 Partially correct 17 ms 8704 KB Partially correct
9 Partially correct 35 ms 18048 KB Partially correct
10 Partially correct 44 ms 24568 KB Partially correct
11 Partially correct 327 ms 198496 KB Partially correct
12 Partially correct 317 ms 198392 KB Partially correct
13 Partially correct 145 ms 88312 KB Partially correct
14 Partially correct 137 ms 88312 KB Partially correct
15 Partially correct 369 ms 211192 KB Partially correct
16 Partially correct 333 ms 211252 KB Partially correct
17 Partially correct 295 ms 179320 KB Partially correct
18 Partially correct 274 ms 179064 KB Partially correct
19 Partially correct 384 ms 212040 KB Partially correct
20 Partially correct 341 ms 211836 KB Partially correct