Submission #643503

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
643503	2022-09-22T08:14:57 Z	BackNoob	Retro (COCI17_retro)	C++14	48 / 100	500 ms	24488 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 || res == dp[1][j][0]) {
            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	Correct	3 ms	6868 KB	Output is correct
2	Correct	3 ms	6872 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	6880 KB	Output is correct
6	Correct	8 ms	7216 KB	Output is correct
7	Partially correct	10 ms	7252 KB	Partially correct
8	Partially correct	8 ms	7124 KB	Partially correct
9	Partially correct	15 ms	7380 KB	Partially correct
10	Correct	16 ms	7500 KB	Output is correct
11	Partially correct	439 ms	19888 KB	Partially correct
12	Partially correct	400 ms	18316 KB	Partially correct
13	Partially correct	211 ms	12412 KB	Partially correct
14	Partially correct	153 ms	12036 KB	Partially correct
15	Execution timed out	675 ms	23712 KB	Time limit exceeded
16	Execution timed out	576 ms	21340 KB	Time limit exceeded
17	Execution timed out	525 ms	19760 KB	Time limit exceeded
18	Partially correct	383 ms	17644 KB	Partially correct
19	Execution timed out	682 ms	24488 KB	Time limit exceeded
20	Execution timed out	599 ms	21268 KB	Time limit exceeded