oj.uz

Submission #238231

# Submission time Handle Problem Language Result Execution time Memory
238231 2020-06-10T09:56:39 Z Vimmer Retro (COCI17_retro) C++14
46 / 100
 179 ms 220408 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
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 108 ms 215928 KB Partially correct
2 Correct 107 ms 216056 KB Output is correct
3 Partially correct 103 ms 216060 KB Partially correct
4 Partially correct 107 ms 215980 KB Partially correct
5 Correct 107 ms 216104 KB Output is correct
6 Partially correct 108 ms 216440 KB Partially correct
7 Partially correct 106 ms 216568 KB Partially correct
8 Partially correct 105 ms 216696 KB Partially correct
9 Partially correct 110 ms 216696 KB Partially correct
10 Partially correct 107 ms 216696 KB Partially correct
11 Partially correct 166 ms 219640 KB Partially correct
12 Partially correct 157 ms 217848 KB Partially correct
13 Partially correct 135 ms 219640 KB Partially correct
14 Partially correct 131 ms 217720 KB Partially correct
15 Partially correct 176 ms 220408 KB Partially correct
16 Partially correct 165 ms 218744 KB Partially correct
17 Partially correct 162 ms 220024 KB Partially correct
18 Partially correct 155 ms 217848 KB Partially correct
19 Partially correct 179 ms 217672 KB Partially correct
20 Partially correct 169 ms 220024 KB Partially correct