oj.uz

Submission #238018

# Submission time Handle Problem Language Result Execution time Memory
238018 2020-06-09T18:03:43 Z Vimmer Retro (COCI17_retro) C++14
52 / 100
 302 ms 427596 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 n, m;

string s[301];

ll pw[55], sm[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);

    cin >> n >> m;

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

    pw[0] = 1;

    for (int i = 1; i < 55; i++) {sm[i] = sm[i - 1] + pw[i - 1]; 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] = {-1, -1};

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

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

    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].F == -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].F, nk = st, val = f[i][j][st].S;

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

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

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

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

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

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

        int i = K - 1;

        while (sz(g) != K)
        {
            if (sm[i] < val)
            {
                val -= pw[i];

                g.pb('(');
            } else g.pb(')');
            i--;
        }

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

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:62:16: warning: variable 'J' set but not used [-Wunused-but-set-variable]
     ll I = -1, J, K = -1, val;
                ^
retro.cpp:85:56: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if (K < f[i][j][0].F || (f[i][j][0].F == K && f[i][j][0].S < val)) {I = i; J = j; K = f[i][j][0].F; val = f[i][j][0].S;}
                                     ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
retro.cpp:51:13: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int sx, sy;
             ^~
retro.cpp:51:9: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int sx, sy;
         ^~

Subtask #1
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 427256 KB Output is correct
2 Correct 188 ms 427260 KB Output is correct
3 Partially correct 188 ms 427256 KB Partially correct
4 Partially correct 195 ms 427256 KB Partially correct
5 Correct 192 ms 427256 KB Output is correct
6 Partially correct 189 ms 427256 KB Partially correct
7 Partially correct 218 ms 427256 KB Partially correct
8 Partially correct 191 ms 427256 KB Partially correct
9 Partially correct 220 ms 427256 KB Partially correct
10 Correct 192 ms 427256 KB Output is correct
11 Partially correct 262 ms 427384 KB Partially correct
12 Partially correct 243 ms 427384 KB Partially correct
13 Partially correct 215 ms 427256 KB Partially correct
14 Partially correct 221 ms 427512 KB Partially correct
15 Partially correct 302 ms 427384 KB Partially correct
16 Partially correct 296 ms 427384 KB Partially correct
17 Partially correct 250 ms 427596 KB Partially correct
18 Partially correct 273 ms 427384 KB Partially correct
19 Partially correct 271 ms 427384 KB Partially correct
20 Partially correct 251 ms 427384 KB Partially correct