Submission #76718

#TimeUsernameProblemLanguageResultExecution timeMemory
76718MilkiRetro (COCI17_retro)C++14
0 / 100
310 ms104444 KiB
#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){ cout << "Ok\n"; 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"; } */ }
#Verdict Execution timeMemoryGrader output
Fetching results...