oj.uz

Submission #643524

# Submission time Handle Problem Language Result Execution time Memory
643524 2022-09-22T09:29:49 Z BackNoob Retro (COCI17_retro) C++14
11 / 100
 500 ms 23092 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][157];
string trace[2][307][157];

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

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];

    for(int j = 1; j <= m; j++) {
        if(a[1][j] == '*') dp[1][j][0] = 0;
        if(a[1][j] == '.') dp[1][j][0] = 0;
        if(a[1][j] == '(') {
            dp[1][j][1] = 1;
            trace[1][j][1] = '(';
        }
    }

    for(int i = 1; i < n; i++) {
        int cur = (i & 1);
        int nxt = ((i + 1) & 1);
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == '*') dp[cur][j][0] = 0;
            for(int k = 0; k <= n / 2; 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(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] == '.' || a[i + 1][j + d] == 'M') {
                            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();
            }
        }
    }

    cout << dp[n & 1][pos.se][0] << endl;
    cout << trace[n & 1][pos.se][0];
}


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;
}

Subtask #1
11.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3668 KB Output is correct
2 Incorrect 2 ms 3668 KB Output isn't correct
3 Partially correct 3 ms 3668 KB Partially correct
4 Incorrect 2 ms 3668 KB Output isn't correct
5 Incorrect 2 ms 3668 KB Output isn't correct
6 Incorrect 6 ms 4052 KB Output isn't correct
7 Incorrect 9 ms 4184 KB Output isn't correct
8 Incorrect 6 ms 3924 KB Output isn't correct
9 Partially correct 9 ms 4180 KB Partially correct
10 Incorrect 9 ms 4228 KB Output isn't correct
11 Incorrect 390 ms 19724 KB Output isn't correct
12 Incorrect 245 ms 16788 KB Output isn't correct
13 Incorrect 98 ms 9472 KB Output isn't correct
14 Incorrect 112 ms 9208 KB Output isn't correct
15 Incorrect 495 ms 22960 KB Output isn't correct
16 Incorrect 442 ms 21312 KB Output isn't correct
17 Incorrect 394 ms 18400 KB Output isn't correct
18 Incorrect 245 ms 15608 KB Output isn't correct
19 Execution timed out 509 ms 23092 KB Time limit exceeded
20 Partially correct 391 ms 20604 KB Partially correct