oj.uz

답안 #643528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643528 2022-09-22T09:46:23 Z BackNoob Retro (COCI17_retro) C++14
40 / 100
 123 ms 113772 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 1e6 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}

int n;
int m;
char a[307][307];
int dp[307][307][307];

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) cin >> a[i][j];

    pair<int, int> pos;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) if(a[i][j] == 'M') pos = make_pair(i, j);

    memset(dp, -0x3f, sizeof(dp));

    for(int j = 1; j <= m; j++) {
        if(a[1][j] == ')') dp[1][j][1] = 1;
        if(a[1][j] == '*') dp[1][j][0] = 0;
        if(a[1][j] == '.') dp[1][j][0] = 0;
    }

    int res = 0;
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == '*') dp[i][j][0] = 0;
            for(int k = 0; k <= n; k++) {
                if(dp[i][j][k] == dp[0][0][0]) continue;
                for(int d = -1; d <= 1; d++) {
                    if(j + d >= 1 && j + d <= m) {
                        if(a[i + 1][j + d] == ')') {
                            maximize(dp[i + 1][j + d][k + 1], dp[i][j][k] + 1);
                        }
                        if(a[i + 1][j + d] == '(') {
                            if(k > 0)
                                maximize(dp[i + 1][j + d][k - 1], dp[i][j][k] + 1);
                        }
                        if(a[i + 1][j + d] == '.' || a[i + 1][j + d] == 'M') {
                            maximize(dp[i + 1][j + d][k], dp[i][j][k]);
                        }
                    }
                }
            }
        }
    }

    cout << dp[n][pos.se][0] << endl;
    for(int i = 0; i < dp[n][pos.se][0]; i++) cout << '(';
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("task.inp", "r", stdin);
    //freopen("graph.out", "w", stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

Compilation message

retro.cpp: In function 'void solve()':
retro.cpp:53:9: warning: unused variable 'res' [-Wunused-variable]
   53 |     int res = 0;
      |         ^~~

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 42 ms 113484 KB Partially correct
2 Partially correct 42 ms 113492 KB Partially correct
3 Partially correct 48 ms 113476 KB Partially correct
4 Partially correct 43 ms 113508 KB Partially correct
5 Partially correct 43 ms 113476 KB Partially correct
6 Partially correct 45 ms 113480 KB Partially correct
7 Partially correct 45 ms 113484 KB Partially correct
8 Partially correct 45 ms 113592 KB Partially correct
9 Partially correct 47 ms 113584 KB Partially correct
10 Partially correct 48 ms 113504 KB Partially correct
11 Partially correct 103 ms 113724 KB Partially correct
12 Partially correct 98 ms 113640 KB Partially correct
13 Partially correct 70 ms 113612 KB Partially correct
14 Partially correct 72 ms 113676 KB Partially correct
15 Partially correct 111 ms 113724 KB Partially correct
16 Partially correct 123 ms 113728 KB Partially correct
17 Partially correct 98 ms 113732 KB Partially correct
18 Partially correct 95 ms 113772 KB Partially correct
19 Partially correct 115 ms 113732 KB Partially correct
20 Partially correct 107 ms 113716 KB Partially correct