oj.uz

Submission #238016

# Submission time Handle Problem Language Result Execution time Memory
238016 2020-06-09T17:54:38 Z Vimmer Retro (COCI17_retro) C++14
40 / 100
 184 ms 214048 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;

string s[301];

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];}

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

        for (int i = 0; i < K; i++) cout << ')';
     }
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:53:16: warning: variable 'J' set but not used [-Wunused-but-set-variable]
     ll I = -1, J, K = -1;
                ^
retro.cpp:51:18: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     f[sx][sy][0] = 0;
     ~~~~~~~~~~~~~^~~
retro.cpp:51:18: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 109 ms 213856 KB Partially correct
2 Partially correct 118 ms 213752 KB Partially correct
3 Partially correct 114 ms 213880 KB Partially correct
4 Partially correct 106 ms 213880 KB Partially correct
5 Partially correct 108 ms 213752 KB Partially correct
6 Partially correct 113 ms 213880 KB Partially correct
7 Partially correct 117 ms 213752 KB Partially correct
8 Partially correct 110 ms 213868 KB Partially correct
9 Partially correct 116 ms 213752 KB Partially correct
10 Partially correct 117 ms 213752 KB Partially correct
11 Partially correct 169 ms 213864 KB Partially correct
12 Partially correct 162 ms 214008 KB Partially correct
13 Partially correct 137 ms 213880 KB Partially correct
14 Partially correct 141 ms 213880 KB Partially correct
15 Partially correct 184 ms 213880 KB Partially correct
16 Partially correct 170 ms 214048 KB Partially correct
17 Partially correct 163 ms 213880 KB Partially correct
18 Partially correct 166 ms 214008 KB Partially correct
19 Partially correct 177 ms 213880 KB Partially correct
20 Partially correct 174 ms 214008 KB Partially correct