Submission #37967

#	Time	Username	Problem	Language	Result	Execution time	Memory
37967		nikhil	Retro (COCI17_retro)	C++14	34 / 100	309 ms	250080 KiB

retro

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

const int N = 502 ;
const int inf = 1e9 ;

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

int solve(int i, int j, int open)
{
    if(open >= N/2 or open < 0) return -inf ;
    if(i == 0 or grid[i][j] == 4)
    {
        if(open) return -inf ;
        return 0;
    }
    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 < (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 ;
        ans = max(ans, bracket + solve(i-1, j+1, open + now)) ;
    }

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

int main()
{
    cin >> n >> m ; char ch ; int si, sj ;
    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 << "()()()" ;
}

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

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

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

Compilation message (stderr)

retro.cpp: In function 'int main()':
retro.cpp:69:28: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout << solve(si, sj, 0) << endl ;
                            ^
retro.cpp:69:28: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 34 / 100