oj.uz

Submission #238022

# Submission time Handle Problem Language Result Execution time Memory
238022 2020-06-09T18:21:54 Z Vimmer Retro (COCI17_retro) C++14
70 / 100
 272 ms 427644 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 i, j, st;

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 (i = n - 1; i > 0; i--)
        for (j = 0; j < m; j++)
          for (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[55 - nw];}

                        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 = 54;

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

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

        for (int i = 0; i < sz(g); i++) cout << g[i];
     }
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:64:16: warning: variable 'J' set but not used [-Wunused-but-set-variable]
     ll I = -1, J, K = -1, val;
                ^
retro.cpp:87: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:53:13: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int sx, sy;
             ^~
retro.cpp:53:9: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int sx, sy;
         ^~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 427256 KB Output is correct
2 Correct 208 ms 427256 KB Output is correct
3 Correct 193 ms 427256 KB Output is correct
4 Correct 195 ms 427256 KB Output is correct
5 Correct 189 ms 427384 KB Output is correct
6 Correct 192 ms 427256 KB Output is correct
7 Correct 214 ms 427256 KB Output is correct
8 Correct 190 ms 427256 KB Output is correct
9 Correct 196 ms 427288 KB Output is correct
10 Correct 197 ms 427236 KB Output is correct
11 Partially correct 253 ms 427384 KB Partially correct
12 Partially correct 245 ms 427428 KB Partially correct
13 Partially correct 230 ms 427384 KB Partially correct
14 Partially correct 217 ms 427256 KB Partially correct
15 Partially correct 272 ms 427644 KB Partially correct
16 Partially correct 262 ms 427384 KB Partially correct
17 Partially correct 256 ms 427384 KB Partially correct
18 Partially correct 256 ms 427440 KB Partially correct
19 Partially correct 267 ms 427384 KB Partially correct
20 Partially correct 259 ms 427384 KB Partially correct