답안 #37967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37967	2017-12-29T18:48:13 Z	nikhil	Retro (COCI17_retro)	C++14	34 / 100	309 ms	250080 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Partially correct	13 ms	250080 KB	Partially correct
2	Incorrect	23 ms	250080 KB	Output isn't correct
3	Partially correct	26 ms	250080 KB	Partially correct
4	Partially correct	26 ms	250080 KB	Partially correct
5	Incorrect	13 ms	250080 KB	Output isn't correct
6	Partially correct	13 ms	250080 KB	Partially correct
7	Incorrect	19 ms	250080 KB	Output isn't correct
8	Partially correct	26 ms	250080 KB	Partially correct
9	Partially correct	26 ms	250080 KB	Partially correct
10	Partially correct	26 ms	250080 KB	Partially correct
11	Partially correct	233 ms	250080 KB	Partially correct
12	Partially correct	223 ms	250080 KB	Partially correct
13	Partially correct	169 ms	250080 KB	Partially correct
14	Partially correct	189 ms	250080 KB	Partially correct
15	Partially correct	309 ms	250080 KB	Partially correct
16	Partially correct	219 ms	250080 KB	Partially correct
17	Partially correct	263 ms	250080 KB	Partially correct
18	Partially correct	233 ms	250080 KB	Partially correct
19	Partially correct	269 ms	250080 KB	Partially correct
20	Partially correct	296 ms	250080 KB	Partially correct