Submission #643501

# Submission time Handle Problem Language Result Execution time Memory
643501 2022-09-22T08:11:25 Z BackNoob Retro (COCI17_retro) C++14
42 / 100
500 ms 24524 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[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[cur][j][k], ')');
                            }
                        }
                        if(a[i - 1][j + d] == '.') {
                            maximize(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:105:9: warning: unused variable 'id' [-Wunused-variable]
  105 |     int id = -1;
      |         ^~
# 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 4 ms 6868 KB Output is correct
6 Correct 11 ms 7244 KB Output is correct
7 Correct 12 ms 7220 KB Output is correct
8 Partially correct 10 ms 7124 KB Partially correct
9 Partially correct 21 ms 7380 KB Partially correct
10 Partially correct 24 ms 7492 KB Partially correct
11 Execution timed out 743 ms 19816 KB Time limit exceeded
12 Execution timed out 567 ms 18276 KB Time limit exceeded
13 Correct 357 ms 12452 KB Output is correct
14 Partially correct 272 ms 12128 KB Partially correct
15 Execution timed out 1066 ms 23776 KB Time limit exceeded
16 Execution timed out 751 ms 21312 KB Time limit exceeded
17 Execution timed out 821 ms 19792 KB Time limit exceeded
18 Execution timed out 582 ms 17732 KB Time limit exceeded
19 Execution timed out 1072 ms 24524 KB Time limit exceeded
20 Execution timed out 776 ms 21208 KB Time limit exceeded