oj.uz

Submission #236103

# Submission time Handle Problem Language Result Execution time Memory
236103 2020-05-31T08:23:27 Z kartel Retro (COCI17_retro) C++14
46 / 100
 176 ms 214648 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))
                {
//                    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))
                {
//                    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))
                {
//                    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 6 ms 1408 KB Partially correct
5 Correct 7 ms 3968 KB Output is correct
6 Partially correct 13 ms 11648 KB Partially correct
7 Partially correct 17 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 24576 KB Partially correct
11 Partially correct 161 ms 200184 KB Partially correct
12 Partially correct 152 ms 200368 KB Partially correct
13 Partially correct 74 ms 87932 KB Partially correct
14 Partially correct 73 ms 87928 KB Partially correct
15 Partially correct 174 ms 212984 KB Partially correct
16 Partially correct 170 ms 212984 KB Partially correct
17 Partially correct 147 ms 179064 KB Partially correct
18 Partially correct 140 ms 179064 KB Partially correct
19 Partially correct 176 ms 214520 KB Partially correct
20 Partially correct 167 ms 214648 KB Partially correct