oj.uz

Submission #236112

# Submission time Handle Problem Language Result Execution time Memory
236112 2020-05-31T08:35:37 Z kartel Retro (COCI17_retro) C++14
46 / 100
 194 ms 214520 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

pair <int, int> f[302][302][302];
int n, m, i, j, b, B, len, ans, I, J;
char c[305][305];

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n >> m;

    for (i = 1; i <= n; i++)
       for (j = 1; j <= m; j++)
         for (b = 0; b <= 300; b++)
            f[i][j][b].F = -1;

    for (i = 1; i <= n; i++)
      for (j = 1; j <= m; j++)
    {
        cin >> c[i][j];

        if (c[i][j] == 'M') f[i][j][0].F = 0;
    }


    for (i = n; i >= 2; i--)
    {
        for (j = 1; j <= m; j++)
            for (b = 0; b <= 300; b++)
        {
            if (f[i][j][b].F == -1) continue;

            if (j - 1 >= 1 && c[i - 1][j - 1] != '*')
            {
                int B = b, len = f[i][j][b].F;

                if (c[i - 1][j - 1] == '(') B++, len++; else
                if (c[i - 1][j - 1] == ')') B--, len++;

                if (B >= 0 && (f[i - 1][j - 1][B].F == -1 || f[i - 1][j - 1][B].F < len || (f[i - 1][j - 1][B].F == len && B - b == 1)))
                {
//                    cerr << len << " " << i - 1 << " " << j - 1 << " " << B << el;
                    f[i - 1][j - 1][B].F = len;
                    f[i - 1][j - 1][B].S = j;
                }

            }

            if (j >= 1 && c[i - 1][j] != '*')
            {
                int B = b, len = f[i][j][b].F;

                if (c[i - 1][j] == '(') B++, len++; else
                if (c[i - 1][j] == ')') B--, len++;

                if (B >= 0 && (f[i - 1][j][B].F == -1 || f[i - 1][j][B].F < len || (f[i - 1][j][B].F == len && B - b == 1)))
                {
//                    cerr << len << " " << i - 1 << " " << j << " " << B << el;
                    f[i - 1][j][B].F = len;
                    f[i - 1][j][B].S = j;
                }

            }

            if (j + 1 <= m && c[i - 1][j + 1] != '*')
            {
                int B = b, len = f[i][j][b].F;

                if (c[i - 1][j + 1] == '(') B++, len++; else
                if (c[i - 1][j + 1] == ')') B--, len++;

                if (B >= 0 && (f[i - 1][j + 1][B].F == -1 || f[i - 1][j + 1][B].F < len || (f[i - 1][j + 1][B].F == len && B - b == 1)))
                {
//                    cerr << len << " " << i - 1 << " " << j + 1 << " " << B << el;
                    f[i - 1][j + 1][B].F = len;
                    f[i - 1][j + 1][B].S = j;
                }
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            if (i == 1 || c[i - 1][j] == '*' || (j - 1 >= 1 && c[i - 1][j - 1] == '*') || (j + 1 <= m && c[i - 1][j + 1] == '*'))
            {
                if (ans < f[i][j][0].F)
                    ans = f[i][j][0].F, I = i, J = j;
            }
        }
    }

    string s = "";

    cout << ans << el;

    b = 0;

    while (I != n)
    {
        int nb = b;

        if (c[I][J] != '.')
        {
            if (c[I][J] == ')') nb++;
                           else nb--;
            s += c[I][J];
        }

        J = f[I][J][b].S;
        I++;

        b = nb;
    }

    reverse(s.begin(), s.end());

    cout << s;
 }

//
//110000
//1100

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 512 KB Partially correct
2 Correct 5 ms 1024 KB Output is correct
3 Partially correct 5 ms 768 KB Partially correct
4 Partially correct 5 ms 1280 KB Partially correct
5 Correct 7 ms 3968 KB Output is correct
6 Partially correct 13 ms 11648 KB Partially correct
7 Partially correct 18 ms 17536 KB Partially correct
8 Partially correct 10 ms 8576 KB Partially correct
9 Partially correct 18 ms 17920 KB Partially correct
10 Partially correct 23 ms 24448 KB Partially correct
11 Partially correct 169 ms 200184 KB Partially correct
12 Partially correct 157 ms 200232 KB Partially correct
13 Partially correct 78 ms 87800 KB Partially correct
14 Partially correct 74 ms 87928 KB Partially correct
15 Partially correct 194 ms 212984 KB Partially correct
16 Partially correct 187 ms 212984 KB Partially correct
17 Partially correct 172 ms 179064 KB Partially correct
18 Partially correct 150 ms 178936 KB Partially correct
19 Partially correct 183 ms 214392 KB Partially correct
20 Partially correct 180 ms 214520 KB Partially correct