oj.uz

Submission #237680

# Submission time Handle Problem Language Result Execution time Memory
237680 2020-06-08T09:33:21 Z Vimmer Retro (COCI17_retro) C++14
49 / 100
 302 ms 427512 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;


pair <ll, ll> f[301][301][301];

ll pw[55];

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

    int n, m;

    cin >> n >> m;

    string s[n];

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

    pw[0] = 1;

    for (int i = 1; i < 55; i++) pw[i] = pw[i - 1] + pw[i - 1];

    int sx, sy;

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

    for (int i = 0; i < 301; i++)
        for (int j = 0; j < 301; j++)
          for (int u = 0; u < 301; u++) f[i][j][u].F = -1;

    f[sx][sy][0] = {0, 0};

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

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

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

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

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

                        if (f[i - 1][j + a][nk].F < nw || (f[i - 1][j + a][nk].F == nw && f[i - 1][j + a][nk].S > st)) f[i - 1][j + a][nk] = {nw, st};
                    }
            }

    for (int i = 0; i < 301; i++)
        for (int j = 0; j < 301; j++)
          for (int u = 0; u < 301; u++)
            if (f[i][j][u].F == u && (K < u || (K == u && st > f[i][j][u].S))) {I = i; J = j; K = u; st = f[i][j][u].S;}

    if (I == -1) cout << 0 << endl;
     else
     {
         cout << K + K << endl;

         int val = K;

         vector <char> g; g.clear();

         while (I != n - 1)
         {
                int pos = -1;

                for (int a = -1; a <= 1; a++)
                  if (a + J < m && a + J >= 0 && f[I + 1][a + J][K].F == val && s[I + 1][a + J] != '#' && f[I + 1][a + J][K].S == st) pos = a + J;

                if (pos == -1)
                {
                    if (s[I][J] == ')')
                    {
                        g.pb(')');

                        val--;

                        for (int a = -1; a <= 1; a++)
                            if (a + J < m && a + J >= 0 && f[I + 1][a + J][K].F == val && s[I + 1][a + J] != '#' && f[I + 1][a + J][K].S == st) pos = a + J;
                    }
                    else
                    {
                        g.pb('(');

                        K--;

                        st -= pw[val + K];

                        for (int a = -1; a <= 1; a++)
                            if (a + J < m && a + J >= 0 && f[I + 1][a + J][K].F == val && s[I + 1][a + J] != '#' && f[I + 1][a + J][K].S == st) pos = a + J;
                    }
                }

                J = pos;

                I++;
         }

         for (int i = sz(g) - 1; i >= 0; i--) cout << g[i];
     }
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:87:56: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if (f[i][j][u].F == u && (K < u || (K == u && st > f[i][j][u].S))) {I = i; J = j; K = u; st = f[i][j][u].S;}
                                                ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
retro.cpp:52:13: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int sx, sy;
             ^~
retro.cpp:52:9: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int sx, sy;
         ^~

Subtask #1
49.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 233 ms 427256 KB Partially correct
2 Correct 233 ms 427256 KB Output is correct
3 Partially correct 230 ms 427256 KB Partially correct
4 Partially correct 268 ms 427256 KB Partially correct
5 Correct 230 ms 427256 KB Output is correct
6 Partially correct 233 ms 427512 KB Partially correct
7 Partially correct 241 ms 427484 KB Partially correct
8 Partially correct 231 ms 427256 KB Partially correct
9 Partially correct 231 ms 427256 KB Partially correct
10 Correct 229 ms 427256 KB Output is correct
11 Partially correct 295 ms 427428 KB Partially correct
12 Partially correct 282 ms 427332 KB Partially correct
13 Partially correct 265 ms 427384 KB Partially correct
14 Partially correct 293 ms 427512 KB Partially correct
15 Partially correct 302 ms 427512 KB Partially correct
16 Partially correct 290 ms 427384 KB Partially correct
17 Partially correct 290 ms 427512 KB Partially correct
18 Partially correct 281 ms 427384 KB Partially correct
19 Partially correct 301 ms 427384 KB Partially correct
20 Partially correct 290 ms 427384 KB Partially correct