Submission #37975

#	Time	Username	Problem	Language	Result	Execution time	Memory
37975		nikhil	Retro (COCI17_retro)	C++14	40 / 100	276 ms	62936 KiB

retro

#include <bits/stdc++.h>
using namespace std ;

const int N = 302 ;
const int inf = 1e5 ;

int dp[N][N][170] ;
int grid[N][N] ;
int n, m ;
string expression ;

int solve(int i, int j, int open)
{
    if(open >= 160 or open < 0) return -inf ;
    if(i == 0 or grid[i][j] == 4)
    {
        if(open == 0) return 0;
        return -inf ;
    }
    if(dp[i][j][open] != -1) return dp[i][j][open] ;

    int ans = 0, now = 0, bracket = 0;

    if(grid[i-1][j] == 3) now = -1, bracket = 1 ;
    else if(grid[i-1][j] == 2) now = 1, bracket = 1 ;

    ans = bracket + solve(i-1, j, open + now) ;

    if(j > 0)
    {
        now = 0, bracket = 0;
        if(grid[i-1][j-1] == 3) now = -1, bracket = 1 ;
        else if(grid[i-1][j-1] == 2) now = 1, bracket = 1 ;
        ans = max(ans, bracket + solve(i-1, j-1, open + now)) ;
    }

    if(j < (m-1))
    {
        now = 0, bracket = 0;
        if(grid[i-1][j+1] == 3) now = -1, bracket = 1 ;
        else if(grid[i-1][j+1] == 2) now = 1, bracket = 1 ;
        ans = max(ans, bracket + solve(i-1, j+1, open + now)) ;
    }

    return dp[i][j][open] = ans ;
}

/*
int prepare(int i, int j, int open)
{
    if(open >= N/2 or open < 0) return -inf ;
    if(i == 0 or grid[i][j] == 4)
        return 0;
    if(dp[i][j][open] != -1) return dp[i][j][open] ;

    if(dp)


    int ans = 0, ans1 = -1, ans2 = -2, now = 0, bracket = 0;

    if(grid[i-1][j] == 3) now = -1, bracket = 1 ;
    else if(grid[i-1][j] == 2) now = 1, bracket = 1 ;

    ans1 = bracket + solve(i-1, j, open + now) ;

    if(j > 0)
    {
        now = 0, bracket = 0;
        if(grid[i-1][j-1] == 3) now = -1, bracket = 1 ;
        else if(grid[i-1][j-1] == 2) now = 1, bracket = 1 ;
        ans2 = bracket + solve(i-1, j-1, open + now) ;
    }

    if(j < (n-1))
    {
        now = 0, bracket = 0;
        if(grid[i-1][j+1] == 3) now = -1, bracket = 1 ;
        else if(grid[i-1][j+1] == 2) now = 1, bracket = 1 ;
        ans3 = bracket + solve(i-1, j+1, open + now) ;
    }

    if(ans1 > ans2 and ans1 > ans3)
    {
        if(grid[i-1][j] == 3) now = -1, expression += ')' ;
        else if(grid[i-1][j] == 2) now = 1, expression += '(' ;
        prepare(i-1, j, open + now);

    }
    else if(ans2 > ans3 and ans2 > ans1)
    {
        if(grid[i-1][j-1] == 3) now = -1, expression += ')' ;
        else if(grid[i-1][j-1] == 2) now = 1, expression += '(' ;
        prepare(i-1, j-1, open + now);

    }
    else if(ans3 > ans1 and ans3 > ans2)
    {
        if(grid[i-1][j+1] == 3) now = -1, expression += ')' ;
        else if(grid[i-1][j+1] == 2) now = 1, expression += '(' ;
        prepare(i-1, j+1, open + now);

    }
    else {
        int up = grid[i][j], upleft, upright ;
        if(ans1 == ans2 and ans2 == ans3)
        {
            upleft = grid[i][j-1], upright = grid[i][j+1] ;
            if(upleft == 2)
                prepare(i, j-1, 1 + open);
            if(upright == 2)
                prepare(i, j+1, 1 + open);
            if(up == 2)
                prepare(i, j+1, 1 + open);
        }
    }
}
*/


int main()
{
    cin >> n >> m ; char ch ; int si = n-1, sj = 0 ;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> ch ;
            if(ch == '.')
                grid[i][j] = 1 ;
            if(ch == '(')
                grid[i][j] = 2 ;
            if(ch == ')')
                grid[i][j] = 3;
            if(ch == '*')
                grid[i][j] = 4 ;
            if(ch == 'M')
                grid[i][j] = 0, si = i, sj = j ;
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(si, sj, 0) << endl ;
    cout << "()()()" ;
    return 0;
}

/*
5 4
..).
.)(.
(.)*
*(.*
..M.

6 3
)(.
*..
(**
)()
().
M..

6 3
((.
*..
(**
)()
().
M..
*/

• Subtask 1: 40 / 100