Submission #643487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
643487	2022-09-22T07:02:51 Z	BackNoob	Retro (COCI17_retro)	C++14	40 / 100	114 ms	113648 KB

retro

#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));

    int res = 0;
    dp[pos.fi][pos.se][0] = 0;
    for(int i = n; i > 1; i--) {
        for(int j = 1; j <= m; j++) {
            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] == '*') {
                            if(k == 0) maximize(res, dp[i][j][k]);
                            continue;
                        }
                        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] == '.') {
                            maximize(dp[i - 1][j + d][k], dp[i][j][k]);
                        }
                    }
                }
            }
        }
    }

    for(int j = 1; j <= m; j++) maximize(res, dp[1][j][0]);
    cout << res << endl;
    for(int j = 0; j < res; j++) cout << '(';
}


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

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

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	52 ms	113524 KB	Partially correct
2	Partially correct	47 ms	113488 KB	Partially correct
3	Partially correct	44 ms	113480 KB	Partially correct
4	Partially correct	49 ms	113452 KB	Partially correct
5	Partially correct	43 ms	113548 KB	Partially correct
6	Partially correct	51 ms	113560 KB	Partially correct
7	Partially correct	46 ms	113480 KB	Partially correct
8	Partially correct	51 ms	113584 KB	Partially correct
9	Partially correct	48 ms	113528 KB	Partially correct
10	Partially correct	47 ms	113588 KB	Partially correct
11	Partially correct	95 ms	113536 KB	Partially correct
12	Partially correct	92 ms	113636 KB	Partially correct
13	Partially correct	69 ms	113540 KB	Partially correct
14	Partially correct	71 ms	113620 KB	Partially correct
15	Partially correct	110 ms	113636 KB	Partially correct
16	Partially correct	96 ms	113644 KB	Partially correct
17	Partially correct	97 ms	113644 KB	Partially correct
18	Partially correct	99 ms	113648 KB	Partially correct
19	Partially correct	114 ms	113612 KB	Partially correct
20	Partially correct	97 ms	113612 KB	Partially correct