답안 #236248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236248	2020-05-31T19:23:00 Z	VEGAnn	Retro (COCI17_retro)	C++14	100 / 100	140 ms	61304 KB

retro

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
#define a3 array<int, 3>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 310;
const int oo = 2e9;
vector<a3> vc, vec[2];
queue<a3> q;
char c[N][N];
short f[N][N][N], ans = 0, n, m;
bool mrk[N][N][N], was[N][N][N];

void upd(short &x, short y){
    x = max(x, y);
}

void check(int i, int j, int sm, int ni, int nj){
    if (c[ni][nj] == '*'){
        return;
    } else if (c[ni][nj] == '.'){
        if (mrk[ni][nj][sm] && f[i][j][sm] == f[ni][nj][sm] && !was[ni][nj][sm]){
            was[ni][nj][sm] = 1;
            q.push({ni, nj, sm});
        }
    } else if (c[ni][nj] == '('){
        if (mrk[ni][nj][sm + 1] && f[i][j][sm] + 1 == f[ni][nj][sm + 1] && !was[ni][nj][sm + 1]){
            was[ni][nj][sm + 1] = 1;
            q.push({ni, nj, sm + 1});
        }
    } else {
        if (sm > 0 && mrk[ni][nj][sm - 1] && f[i][j][sm] + 1 == f[ni][nj][sm - 1] && !was[ni][nj][sm - 1]){
            was[ni][nj][sm - 1] = 1;
            q.push({ni, nj, sm - 1});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

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

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    for (int sm = 0; sm <= i; sm++)
        f[i][j][sm] = -1;

    for (int j = 0; j < m; j++)
        if (c[0][j] == 'M') {
            f[0][j][0] = 0;
            vc.PB({0, j, 0});
        }

    for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < m; j++)
    for (int sm = 0; sm <= i; sm++){
        if (f[i][j][sm] < 0) continue;

        for (int stp = -1; stp < 2; stp++){
            int ni = i + 1, nj = j + stp;

            if (nj < 0 || nj >= m) continue;

            if (c[ni][nj] == '*'){
                if (sm == 0) {
                    upd(ans, f[i][j][sm]);
                }
            } else if (c[ni][nj] == '.'){
                upd(f[ni][nj][sm], f[i][j][sm]);
            } else if (c[ni][nj] == '('){
                upd(f[ni][nj][sm + 1], f[i][j][sm] + 1);
            } else if (sm > 0){
                upd(f[ni][nj][sm - 1], f[i][j][sm] + 1);
            }
        }
    }

    for (int j = 0; j < m; j++)
        ans = max(ans, f[n - 1][j][0]);

    cout << ans << '\n';

    for (int j = 0; j < m; j++)
        if (f[n - 1][j][0] == ans)
            mrk[n - 1][j][0] = 1;

    for (int i = n - 2; i >= 0; i--){
        for (int j = 0; j < m; j++)
        for (int sm = 0; sm <= i; sm++){
            if (f[i][j][sm] < 0) continue;

            for (int stp = -1; stp < 2 && !mrk[i][j][sm]; stp++){
                int ni = i + 1, nj = j + stp;

                if (nj < 0 || nj >= m) continue;

                if (c[ni][nj] == '*'){
                    if (sm == 0 && ans == f[i][j][sm])
                        mrk[i][j][sm] = 1;
                } else if (c[ni][nj] == '.'){
                    if (mrk[ni][nj][sm] && f[i][j][sm] == f[ni][nj][sm])
                        mrk[i][j][sm] = 1;
                } else if (c[ni][nj] == '('){
                    if (mrk[ni][nj][sm + 1] && f[i][j][sm] + 1 == f[ni][nj][sm + 1])
                        mrk[i][j][sm] = 1;
                } else {
                    if (sm > 0 && mrk[ni][nj][sm - 1] && f[i][j][sm] + 1 == f[ni][nj][sm - 1])
                        mrk[i][j][sm] = 1;
                }
            }
        }
    }

    for (int itr = 0; itr < ans; itr++){
        vec[0].clear();
        vec[1].clear();

        for (a3 st : vc){
            int i = st[0], j = st[1], sm = st[2];

            for (int stp = -1; stp < 2; stp++){
                int ni = i + 1, nj = j + stp;

                if (nj < 0 || nj >= m) continue;

                if (c[ni][nj] == '*') continue;

                check(i, j, sm, ni, nj);
            }
        }

        while (sz(q)){
            a3 cr = q.front(); q.pop();

            int i = cr[0], j = cr[1], sm = cr[2];

            if (c[i][j] == '('){
                vec[0].PB({i, j, sm});
                continue;
            }

            if (c[i][j] == ')'){
                vec[1].PB({i, j, sm});
                continue;
            }

            for (int stp = -1; stp < 2; stp++){
                int ni = i + 1, nj = j + stp;

                if (nj < 0 || nj >= m) continue;

                if (c[ni][nj] == '*') continue;

                check(i, j, sm, ni, nj);
            }
        }

        if (sz(vec[0]) > 0){
            cout << "(";

            vc = vec[0];
        } else {
            cout << ")";

            vc = vec[1];
        }
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	512 KB	Output is correct
2	Correct	5 ms	640 KB	Output is correct
3	Correct	5 ms	640 KB	Output is correct
4	Correct	5 ms	768 KB	Output is correct
5	Correct	5 ms	1536 KB	Output is correct
6	Correct	8 ms	4224 KB	Output is correct
7	Correct	9 ms	6016 KB	Output is correct
8	Correct	8 ms	3840 KB	Output is correct
9	Correct	10 ms	6272 KB	Output is correct
10	Correct	12 ms	7936 KB	Output is correct
11	Correct	121 ms	56952 KB	Output is correct
12	Correct	111 ms	55416 KB	Output is correct
13	Correct	56 ms	28664 KB	Output is correct
14	Correct	57 ms	26744 KB	Output is correct
15	Correct	140 ms	61276 KB	Output is correct
16	Correct	114 ms	59640 KB	Output is correct
17	Correct	112 ms	52344 KB	Output is correct
18	Correct	96 ms	50168 KB	Output is correct
19	Correct	131 ms	59000 KB	Output is correct
20	Correct	117 ms	61304 KB	Output is correct