oj.uz

답안 #237683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237683 2020-06-08T09:46:34 Z Vimmer Retro (COCI17_retro) C++14
5 / 100
 346 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 == -1 || f[i - 1][j + a][nk].S > st || (f[i - 1][j + a][nk].S == st && f[i - 1][j + a][nk].F < nw)) 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)
         {
                //cout << I << " " << J << " " << K << " " << val << " " << st << endl;

                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
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 283 ms 427256 KB Output is correct
2 Incorrect 274 ms 427256 KB Output isn't correct
3 Incorrect 254 ms 427384 KB Output isn't correct
4 Incorrect 280 ms 427256 KB Output isn't correct
5 Incorrect 280 ms 427256 KB Output isn't correct
6 Incorrect 225 ms 427256 KB Output isn't correct
7 Incorrect 231 ms 427384 KB Output isn't correct
8 Incorrect 232 ms 427384 KB Output isn't correct
9 Incorrect 232 ms 427256 KB Output isn't correct
10 Incorrect 242 ms 427256 KB Output isn't correct
11 Incorrect 292 ms 427384 KB Output isn't correct
12 Incorrect 286 ms 427384 KB Output isn't correct
13 Incorrect 313 ms 427384 KB Output isn't correct
14 Incorrect 265 ms 427256 KB Output isn't correct
15 Incorrect 307 ms 427388 KB Output isn't correct
16 Incorrect 346 ms 427512 KB Output isn't correct
17 Incorrect 295 ms 427512 KB Output isn't correct
18 Incorrect 340 ms 427384 KB Output isn't correct
19 Incorrect 309 ms 427384 KB Output isn't correct
20 Incorrect 303 ms 427384 KB Output isn't correct