Submission #643502

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
643502	2022-09-22T08:14:12 Z	BackNoob	Retro (COCI17_retro)	C++14	48 / 100	500 ms	24524 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) {
                                if(maximize(res, dp[cur][j][k]) == true || res == dp[cur][j][k]) {
                                    upd(ans, trace[cur][j][k]);
                                }
                            }
                            continue;
                        }
                        if(a[i - 1][j + d] == '(') {
                            if(maximize(dp[nxt][j + d][k + 1], dp[cur][j][k] + 1) == true || 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) {
                                if(maximize(dp[nxt][j + d][k - 1], dp[cur][j][k] + 1) == true || 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(maximize(dp[nxt][j + d][k], dp[cur][j][k]) == true && dp[nxt][j + d][k] == dp[cur][j][k])
                                upd(trace[nxt][j + d][k], trace[cur][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;
    cout << ans;
}


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:107:9: warning: unused variable 'id' [-Wunused-variable]
  107 |     int id = -1;
      |         ^~

Subtask #1

48.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	3 ms	6868 KB	Partially correct
2	Correct	4 ms	6868 KB	Output is correct
3	Partially correct	3 ms	6868 KB	Partially correct
4	Correct	3 ms	6868 KB	Output is correct
5	Correct	3 ms	6868 KB	Output is correct
6	Correct	8 ms	7204 KB	Output is correct
7	Partially correct	9 ms	7260 KB	Partially correct
8	Partially correct	8 ms	7124 KB	Partially correct
9	Partially correct	16 ms	7400 KB	Partially correct
10	Partially correct	16 ms	7380 KB	Partially correct
11	Partially correct	420 ms	19788 KB	Partially correct
12	Partially correct	344 ms	18376 KB	Partially correct
13	Partially correct	173 ms	12504 KB	Partially correct
14	Partially correct	144 ms	12124 KB	Partially correct
15	Execution timed out	613 ms	23788 KB	Time limit exceeded
16	Partially correct	458 ms	21328 KB	Partially correct
17	Partially correct	452 ms	19844 KB	Partially correct
18	Partially correct	330 ms	17612 KB	Partially correct
19	Execution timed out	640 ms	24524 KB	Time limit exceeded
20	Partially correct	465 ms	21196 KB	Partially correct