oj.uz

Submission #238226

# Submission time Handle Problem Language Result Execution time Memory
238226 2020-06-10T09:34:31 Z Vimmer Retro (COCI17_retro) C++14
49 / 100
 191 ms 220412 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


ll f[301][301][301], n, m;

vector <char> ans;

string s[301];

vector <char> bst[301][301];

bool mk[301][301][301], mkr[301][301];

bool low(vector <char> &a, vector <char> &b)
{
    for (int i = 0; i < sz(a); i++)
    {
        if (a[i] == b[i]) continue;

        return a[i] == '(';
    }

    return 0;
}

priority_queue <array <int, 3> > qr;

void solve(int i, int j, int b, int len)
{
    if (mk[i][j][b]) return;

    mk[i][j][b] = 1;

    if (i == n - 1) return;

    if (s[i][j] == '(') {b--; len--; }

    if (s[i][j] == ')') {b++; len--; }

    for (int a = -1; a <= 1; a++)
    {
        int nb = b, nlen = len, jr = j + a;

        if (jr < 0 || jr == m || s[i + 1][jr] == '*') continue;

        if (nb == -1) continue;

        if (f[i + 1][jr][nb] == nlen) solve(i + 1, jr, nb, nlen);
    }

}
int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> s[i];

    int sx, sy;

    for (int i = 0; i < m; i++)
        if (s[n - 1][i] == 'M') {sx = n - 1; sy = i; break;}

    memset(f, -1, sizeof(f));

    f[sx][sy][0] = 0;

    ll I = -1, J, K = -1;

    for (int i = n - 1; i > 0; i--)
        for (int j = 0; j < m; j++)
          for (int st = 0; st <= n - i - 1; st++)
            {
                if (f[i][j][st] == -1 || s[i][j] == '*') continue;

                for (int a = -1; a <= 1; a++)
                    if (a + j >= 0 && a + j < m && (st != 0 || s[i - 1][j + a] != ')'))
                    {
                        ll nw = f[i][j][st], nk = st;

                        if (s[i - 1][j + a] == '(') {nw++; nk++;}

                        if (s[i - 1][j + a] == ')') {nw++; nk--;}

                        if (f[i - 1][j + a][nk] == -1 || f[i - 1][j + a][nk] < nw) f[i - 1][j + a][nk] = nw;
                    }
            }

    for (int i = 0; i < 301; i++)
        for (int j = 0; j < 301; j++)
            if (K < f[i][j][0]) {I = i; J = j; K = f[i][j][0];}

    for (int i = 0; i < 301; i++)
        for (int j = 0; j < 301; j++)
          if (f[i][j][0] == K) solve(i, j, 0, K);

    cout << K << endl;

    qr.push({0, sx, sy});

    while (sz(qr) > 0)
    {
        int tp = qr.top()[0], i = qr.top()[1], j = qr.top()[2];

        qr.pop();

        if (tp == 1) bst[i][j].pb('(');

        if (tp == 2) bst[i][j].pb(')');

        if (sz(bst[i][j]) == K)
        {
            if (sz(ans) == 0 || low(bst[i][j], ans)) ans = bst[i][j];

            continue;
        }

        int len = sz(bst[i][j]), b = 0;

        for (auto it : bst[i][j])
            if (it == '(') b++;

        b = b + b - sz(bst[i][j]);

        for (int a = -1; a <= 1; a++)
        {
            int jr = j + a, nlen = len, nb = b, tp = 0;

            if (jr < 0 || jr == m || s[i - 1][jr] == '*' || mkr[i - 1][jr]) continue;

            if (s[i - 1][jr] == '(') {tp = 1; nb++; nlen++;}

            if (s[i - 1][jr] == ')') {tp = 2; nb--; nlen++;}

            if (nb == -1) continue;

            if (mk[i - 1][jr][nb] && f[i - 1][jr][nb] == nlen) {mkr[i - 1][jr] = 1; bst[i - 1][jr] = bst[i][j]; qr.push({tp, i - 1, jr}); }
        }
    }

    for (auto it : ans) cout << it;
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:97:8: warning: variable 'I' set but not used [-Wunused-but-set-variable]
     ll I = -1, J, K = -1;
        ^
retro.cpp:97:16: warning: variable 'J' set but not used [-Wunused-but-set-variable]
     ll I = -1, J, K = -1;
                ^
retro.cpp:95:18: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     f[sx][sy][0] = 0;
     ~~~~~~~~~~~~~^~~
retro.cpp:95:18: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
49.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 215928 KB Output is correct
2 Correct 105 ms 216056 KB Output is correct
3 Partially correct 111 ms 216056 KB Partially correct
4 Partially correct 106 ms 216056 KB Partially correct
5 Correct 106 ms 216056 KB Output is correct
6 Partially correct 110 ms 216544 KB Partially correct
7 Partially correct 108 ms 216568 KB Partially correct
8 Partially correct 120 ms 216696 KB Partially correct
9 Partially correct 109 ms 216696 KB Partially correct
10 Partially correct 109 ms 216568 KB Partially correct
11 Partially correct 187 ms 219640 KB Partially correct
12 Partially correct 162 ms 217976 KB Partially correct
13 Partially correct 137 ms 219640 KB Partially correct
14 Partially correct 134 ms 217736 KB Partially correct
15 Partially correct 179 ms 220412 KB Partially correct
16 Partially correct 166 ms 218616 KB Partially correct
17 Partially correct 191 ms 220024 KB Partially correct
18 Partially correct 158 ms 217840 KB Partially correct
19 Partially correct 177 ms 217620 KB Partially correct
20 Partially correct 166 ms 219896 KB Partially correct