Submission #37968

#	Time	Username	Problem	Language	Result	Execution time	Memory
37968		nikhil	Retro (COCI17_retro)	C++14	34 / 100	326 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 < (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 = 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;
}

• Subtask 1: 34 / 100