Submission #643500

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
643500	2022-09-22T08:10:43 Z	BackNoob	Retro (COCI17_retro)	C++14	40 / 100	64 ms	7116 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[2][307][307];
string trace[2][307][307];

void upd(string &a, string b, char c = ' ')
{
    if(c != ' ') b += c;
    if(sz(a) > sz(b)) return;
    if(sz(a) < sz(b)) {
        a = b;
    }
    else {
        for(int i = 0; i < sz(a); i++) {
            if(a[i] == b[i]) continue;
            if(a[i] > b[i]) a = b;
            return;
        }
    }
}

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 tmp = dp[0][0][0];

    int res = 0;
    string ans = "";
    dp[n & 1][pos.se][0] = 0;
    for(int i = n; i > 1; i--) {
        int cur = (i & 1);
        int nxt = ((i - 1) & 1);
        for(int j = 1; j <= m; j++) {
            for(int k = 0; k <= n; k++) {
                if(dp[cur][j][k] == tmp) 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[cur][j][k]);
                                //upd(ans, trace[cur][j][k]);
                            }
                            continue;
                        }
                        if(a[i - 1][j + d] == '(') {
                            maximize(dp[nxt][j + d][k + 1], dp[cur][j][k] + 1);
                            //upd(trace[nxt][j + d][k + 1], trace[cur][j][k], '(');
                        }
                        if(a[i - 1][j + d] == ')') {
                            if(k > 0) {
                                maximize(dp[nxt][j + d][k - 1], dp[cur][j][k] + 1);
                                //upd(trace[nxt][j + d][k - 1], trace[i][j][k], ')');
                            }
                        }
                        if(a[i - 1][j + d] == '.') {
                            maximize(dp[nxt][j + d][k], dp[cur][j][k]);
                            //upd(trace[i - 1][j + d][k], trace[i][j][k]);
                        }
                    }
                }
                dp[cur][j][k] = tmp;
                trace[cur][j][k].clear();
            }
        }
    }

    int id = -1;
    for(int j = 1; j <= m; j++) {
        if(maximize(res, dp[1][j][0]) == true) {
            upd(ans, trace[1][j][0]);
        }
    }

    cout << res << endl;
    for(int i = 0; i < res; 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:105:9: warning: unused variable 'id' [-Wunused-variable]
  105 |     int id = -1;
      |         ^~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	3 ms	6868 KB	Partially correct
2	Partially correct	3 ms	6868 KB	Partially correct
3	Partially correct	3 ms	6868 KB	Partially correct
4	Partially correct	4 ms	6868 KB	Partially correct
5	Partially correct	4 ms	6868 KB	Partially correct
6	Partially correct	6 ms	6868 KB	Partially correct
7	Partially correct	5 ms	6988 KB	Partially correct
8	Partially correct	4 ms	6868 KB	Partially correct
9	Partially correct	7 ms	7004 KB	Partially correct
10	Partially correct	6 ms	6868 KB	Partially correct
11	Partially correct	53 ms	6996 KB	Partially correct
12	Partially correct	52 ms	7032 KB	Partially correct
13	Partially correct	26 ms	6996 KB	Partially correct
14	Partially correct	29 ms	6996 KB	Partially correct
15	Partially correct	64 ms	7032 KB	Partially correct
16	Partially correct	55 ms	7040 KB	Partially correct
17	Partially correct	52 ms	6996 KB	Partially correct
18	Partially correct	52 ms	7116 KB	Partially correct
19	Partially correct	62 ms	6996 KB	Partially correct
20	Partially correct	53 ms	7028 KB	Partially correct