Submission #236110

# Submission time Handle Problem Language Result Execution time Memory
236110 2020-05-31T08:32:44 Z ne4eHbKa Retro (COCI17_retro) C++17
88 / 100
367 ms 333784 KB
//{ <defines>
#include <bits/stdc++.h>
using namespace std;

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

int md = 998244353;

inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}

int m_bpow(ll A, ll b) {
    int a = A % md;
    ll ans = 1;
    for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
        (ans *= ans) %= md;
        if(p & b)
            (ans *= a) %= md;
    }
    re ans;
}

//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 305;

int f[N][N][N];
int pr[N][N][N];
int o[N][N][N];
string s[N];

int n, m;

pair<int, int> c(int i, int j, int b) {
    if(j >= 0 && j < m && (i < 0 || s[i][j] == '*') && !b) re {0, 0};
    if(i < 0 || j < 0 || j >= m || b < 0 || b > i + 1 || s[i][j] == '*') re {-1, 0};
    int &ans = f[i][j][b], &p = pr[i][j][b], &op = o[i][j][b];
    if(ans < oo) re {ans, op};
    bool br = false;
    if(s[i][j] == ')') --b, br = true;
    if(s[i][j] == '(') ++b, br = true;
    ans = p = -1;
    for(int z = j - 1; z <= j + 1; ++z) {
        auto v = c(i - 1, z, b);
        if(~v.ft) {
            int u = v.ft + br;
            if(u > ans || u == ans && v.sd > op) {
                ans = u;
                op = v.sd;
                p = z;
            }
        }
    }
    if(s[i][j] == '(') ++op;
    if(s[i][j] == ')') op = 0;
    re {ans, op};
}

void ans(int i, int j, int b) {
    if(i < 0 || s[i][j] == '*') re;
    if(s[i][j] != '.' && s[i][j] != 'M') cout << s[i][j];
    ans(i - 1, pr[i][j][b], b + (s[i][j] == '(' ? +1 : s[i][j] == ')' ? -1 : 0));
}

void solve() {
    clr(f, 127);
    clr(pr, -1);
    clr(o, 0);
    cin >> n >> m;
    fo(n) cin >> s[i];
    int M {};
    for(int i = 0; i < m; ++i) if(s[n - 1][i] == 'M') M = i;
    int v = c(n - 1, M, 0).ft, b = 0;
    cout << v << endl;
    ans(n - 1, M, 0);
    cout << endl;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    for(int test = 1; test <= tests; ++test) {
		cerr << "case #" << test << endl;
        solve();
        cerr << endl;
    }
#else
//    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#endif
    return 0;
}

Compilation message

retro.cpp: In function 'int m_bpow(ll, ll)':
retro.cpp:50:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~
retro.cpp: In function 'std::pair<int, int> c(int, int, int)':
retro.cpp:85:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if(u > ans || u == ans && v.sd > op) {
                           ~~~~~~~~~^~~~~~~~~~~~
retro.cpp: In function 'void solve()':
retro.cpp:111:32: warning: unused variable 'b' [-Wunused-variable]
     int v = c(n - 1, M, 0).ft, b = 0;
                                ^
# Verdict Execution time Memory Grader output
1 Correct 171 ms 333432 KB Output is correct
2 Correct 172 ms 333432 KB Output is correct
3 Correct 171 ms 333432 KB Output is correct
4 Correct 175 ms 333452 KB Output is correct
5 Correct 182 ms 333560 KB Output is correct
6 Correct 178 ms 333560 KB Output is correct
7 Partially correct 176 ms 333692 KB Partially correct
8 Partially correct 181 ms 333644 KB Partially correct
9 Correct 177 ms 333432 KB Output is correct
10 Correct 181 ms 333560 KB Output is correct
11 Correct 322 ms 333688 KB Output is correct
12 Partially correct 301 ms 333560 KB Partially correct
13 Partially correct 238 ms 333560 KB Partially correct
14 Correct 245 ms 333652 KB Output is correct
15 Correct 367 ms 333560 KB Output is correct
16 Correct 323 ms 333784 KB Output is correct
17 Correct 335 ms 333560 KB Output is correct
18 Correct 322 ms 333560 KB Output is correct
19 Correct 365 ms 333560 KB Output is correct
20 Correct 327 ms 333688 KB Output is correct