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

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[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;
      |         ^~

Subtask #1

42.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	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