Submission #76719

#	Time	Username	Problem	Language	Result	Execution time	Memory
76719		Milki	Retro (COCI17_retro)	C++14	71 / 100	337 ms	104444 KiB

retro

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 302;

int dp[MAXN][MAXN][MAXN];
bool ok[MAXN][MAXN][MAXN];
int n, m, len;
char a[MAXN][MAXN];
bool mogu[MAXN][MAXN];
unordered_map<int, unordered_map<int, unordered_map <int, string> > > bio;

point mirko;
string sol;

void construct(int x, int y, int diff){
    if(ok[x][y][diff]) return;
    //cout << x _ y _ diff << " banana\n";
    ok[x][y][diff] = true;

    int nx = x + 1;
    int ny = y - 1;

    int val = 0;
    if(a[x][y] == '(') val = -1;
    else if(a[x][y] == ')') val = 1;

    REP(i, 3){
        if(a[nx][ny] == '*' || ny < 0 || ny >= m || nx >= n){
            ny ++;
            continue;
        }
        //cout << dp[nx][ny][diff + val] + (int)(val != 0) _ dp[x][y][diff] _ val _ diff + val _ "   aaaaa\n";
        if(dp[nx][ny][diff + val] + (int)(val != 0) == dp[x][y][diff])
            construct(nx, ny, diff + val);

        ny ++;
    }
}

struct state{
    int x, y, diff, lx, ly, ldiff;
};

void bfs(){
    queue <state> Q;
    Q.push({mirko.first, mirko.second, 0, MAXN - 1, MAXN - 1, 0});

    while(!Q.empty()){
        state kord = Q.front();
        Q.pop();

        int x = kord.x, y = kord.y, diff = kord.diff;

        int val = 0;
        if(a[x][y] == '(') val = 1;
        else if(a[x][y] == ')') val = -1;
        diff += val;

        //cout << x _ y _ diff _ " pls radi\n";
        //cout << " good zivot \n";
        if(!ok[x][y][diff] || x < 0 || y < 0 || y >= m) continue;
        //cout << " usrani zivot\n";
        if(sz(bio[x][y][diff])){
            //cout << "why\n";
            if(a[x][y] == '.' && sz(bio[kord.lx][kord.ly][kord.ldiff]) == sz(bio[x][y][diff]))
                bio[x][y][diff] = min(bio[x][y][diff], bio[kord.lx][kord.ly][kord.ldiff]);
            else if((a[x][y] == '(' || a[x][y] == ')') && sz(bio[kord.lx][kord.ly][kord.ldiff]) + 1 == sz(bio[x][y][diff]))
                bio[x][y][diff] = min(bio[x][y][diff], bio[kord.lx][kord.ly][kord.ldiff] + a[x][y]);
        }
        else if(a[x][y] != '*'){
            //cout << "zivote\n";
            if(a[x][y] == '(' || a[x][y] == ')'){
                bio[x][y][diff] = bio[kord.lx][kord.ly][kord.ldiff] + a[x][y];
                //cout << bio[x][y][diff] << " alalaal\n";
            }
            else{
                bio[x][y][diff] = bio[kord.lx][kord.ly][kord.ldiff];
               // cout << x _ y _ diff << " troll je bol\n";
            }

            Q.push({x - 1, y - 1, diff, x, y, diff}); Q.push({x - 1, y, diff, x, y, diff}); Q.push({x - 1, y + 1, diff, x, y, diff});
        }
    }
}

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

    cin >> n >> m;
    REP(i, n)
        REP(j, m)
            cin >> a[i][j];

    REP(j, m)
        if(a[n - 1][j] == 'M'){
            mirko = point(n - 1, j);
            break;
        }

    int y = mirko.second;
    int bounds = 1;

    for(int i = n - 2; i >= 0; --i){
        mogu[i][y] = true;

        for(int j = y + 1; j <= min(m - 1, y + bounds); ++j)
            mogu[i][j] = true;

        for(int j = y - 1; j >= max(0, y - bounds); --j)
            mogu[i][j] = true;

        bounds ++;
    }
    mogu[mirko.first][mirko.second] = true;

    for(int i = n - 2; i >= 0; --i){
        REP(k, n){
            REP(j, m){
                if(a[i][j] == '*' || !mogu[i][j]) continue;
                int val1 = 0, val2 = 0, val3 = 0;

                if(a[i][j] == '.'){
                    if(j) val1 = dp[i + 1][j - 1][k];
                    val2 = dp[i + 1][j][k];
                    if(j != m - 1) val3 = dp[i + 1][j + 1][k];

                    dp[i][j][k] = max( max(val1, val2), max(dp[i][j][k], val3));
                }
                else if(a[i][j] == '(' && k > 0){
                    if(k != 1){
                        if(j && dp[i + 1][j - 1][k - 1]) val1 = dp[i + 1][j - 1][k - 1] + 1;
                        if(dp[i + 1][j][k - 1]) val2 = dp[i + 1][j][k - 1] + 1;
                        if(j != m - 1 && dp[i + 1][j + 1][k - 1]) val3 = dp[i + 1][j + 1][k - 1] + 1;
                    }
                    else{
                        if(j) val1 = dp[i + 1][j - 1][k - 1] + 1;
                        val2 = dp[i + 1][j][k - 1] + 1;
                        if(j != m - 1) val3 = dp[i + 1][j + 1][k - 1] + 1;
                    }
                    dp[i][j][k] = max( max(val1, val2), max(dp[i][j][k], val3));
                }
                else if(a[i][j] == ')'){
                    if(k){
                        if(j && dp[i + 1][j - 1][k + 1]) val1 = dp[i + 1][j - 1][k + 1] + 1;
                        if(dp[i + 1][j][k + 1]) val2 = dp[i + 1][j][k + 1] + 1;
                        if(j != m - 1 && dp[i + 1][j + 1][k + 1]) val3 = dp[i + 1][j + 1][k + 1] + 1;
                    }
                    else{
                        if(j && dp[i + 1][j - 1][k + 1] % 2) val1 = dp[i + 1][j - 1][k + 1] + 1;
                        if(dp[i + 1][j][k + 1] % 2) val2 = dp[i + 1][j][k + 1] + 1;
                        if(j != m - 1 && dp[i + 1][j + 1][k + 1] % 2) val3 = dp[i + 1][j + 1][k + 1] + 1;
                    }
                    dp[i][j][k] = max( max(val1, val2), max(dp[i][j][k], val3));
                }
            }
        }
        REP(j, m)
            len = max(len, dp[i][j][0]);
    }

    REP(i, n)
        REP(j, m)
            if(dp[i][j][0] == len){
                construct(i, j, 0);
                //cout << "sve " _ i _ j _ 0 << "\n";
            }

    REP(i, 301)
        sol += ')';

    bfs();

    cout << len << "\n";

    REP(i, n)
        REP(j, m){
            if(sz(bio[i][j][0]) == len){
                sol = min(sol, bio[i][j][0]);
            }
        }
    cout << sol << "\n";

    /*REP(k, n / 2){
        REP(i, n){
            REP(j, m)
                cout << dp[i][j][k];
            cout << "\n";
        }
        cout << "\n\n\n";
    } */
}

• Subtask 1: 71 / 100