답안 #37975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37975	2017-12-29T19:25:06 Z	nikhil	Retro (COCI17_retro)	C++14	40 / 100	276 ms	62936 KB

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	62936 KB	Partially correct
2	Partially correct	3 ms	62936 KB	Partially correct
3	Partially correct	6 ms	62936 KB	Partially correct
4	Partially correct	6 ms	62936 KB	Partially correct
5	Partially correct	9 ms	62936 KB	Partially correct
6	Partially correct	13 ms	62936 KB	Partially correct
7	Partially correct	6 ms	62936 KB	Partially correct
8	Partially correct	6 ms	62936 KB	Partially correct
9	Partially correct	16 ms	62936 KB	Partially correct
10	Partially correct	13 ms	62936 KB	Partially correct
11	Partially correct	196 ms	62936 KB	Partially correct
12	Partially correct	166 ms	62936 KB	Partially correct
13	Partially correct	89 ms	62936 KB	Partially correct
14	Partially correct	86 ms	62936 KB	Partially correct
15	Partially correct	263 ms	62936 KB	Partially correct
16	Partially correct	213 ms	62936 KB	Partially correct
17	Partially correct	233 ms	62936 KB	Partially correct
18	Partially correct	169 ms	62936 KB	Partially correct
19	Partially correct	276 ms	62936 KB	Partially correct
20	Partially correct	246 ms	62936 KB	Partially correct