| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 76496 | 2018-09-13T21:33:27 Z | Milki | Retro (COCI17_retro) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(short i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((short) x.size())
#define pb(x) push_back(x)
typedef long long ll;
typedef pair<short, short> poshort;
const short MAXN = 302;
short dp[MAXN][MAXN][MAXN];
bool ok[MAXN][MAXN][MAXN];
short n, m, len;
char a[MAXN][MAXN];
bool mogu[MAXN][MAXN];
string bio[MAXN][MAXN][MAXN];
poshort mirko;
string sol;
void construct(short x, short y, short diff){
if(ok[x][y][diff]) return;
//cout << x _ y _ diff << " banana\n";
ok[x][y][diff] = true;
short nx = x + 1;
short ny = y - 1;
short 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] + (short)(val != 0) _ dp[x][y][diff] _ val _ diff + val _ " aaaaa\n";
if(dp[nx][ny][diff + val] + (short)(val != 0) == dp[x][y][diff])
construct(nx, ny, diff + val);
ny ++;
}
}
struct state{
short 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();
short x = kord.x, y = kord.y, diff = kord.diff;
short 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});
}
}
}
short 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 = poshort(n - 1, j);
break;
}
short y = mirko.second;
short bounds = 1;
for(short i = n - 2; i >= 0; --i){
mogu[i][y] = true;
for(short j = y + 1; j <= min(m - 1, y + bounds); ++j)
mogu[i][j] = true;
for(short j = y - 1; j >= max(0, y - bounds); --j)
mogu[i][j] = true;
bounds ++;
}
mogu[mirko.first][mirko.second] = true;
for(short i = n - 2; i >= 0; --i){
REP(k, n){
REP(j, m){
if(a[i][j] == '*' || !mogu[i][j]) continue;
short 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(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(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));
}
}
}
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, n){
if(sz(bio[i][j][0]) == len){
sol = min(sol, bio[i][j][0]);
}
}
cout << sol;
}