oj.uz

Submission #37967

# Submission time Handle Problem Language Result Execution time Memory
37967 2017-12-29T18:48:13 Z nikhil Retro (COCI17_retro) C++14
34 / 100
 309 ms 250080 KB 
#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

# Verdict Execution time Memory 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