Submission #643528

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
643528	2022-09-22T09:46:23 Z	BackNoob	Retro (COCI17_retro)	C++14	40 / 100	123 ms	113772 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));

    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

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