Submission #76496

#TimeUsernameProblemLanguageResultExecution timeMemory
76496MilkiRetro (COCI17_retro)C++14
Compilation error
0 ms0 KiB
#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; }

Compilation message (stderr)

retro.cpp: In function 'void bfs()':
retro.cpp:91:23: warning: narrowing conversion of '(((int)x) - 1)' from 'int' to 'short int' inside { } [-Wnarrowing]
             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});
                     ~~^~~
retro.cpp:91:30: warning: narrowing conversion of '(((int)y) - 1)' from 'int' to 'short int' inside { } [-Wnarrowing]
             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});
                            ~~^~~
retro.cpp:91:65: warning: narrowing conversion of '(((int)x) - 1)' from 'int' to 'short int' inside { } [-Wnarrowing]
             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});
                                                               ~~^~~
retro.cpp:91:103: warning: narrowing conversion of '(((int)x) - 1)' from 'int' to 'short int' inside { } [-Wnarrowing]
             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});
                                                                                                     ~~^~~
retro.cpp:91:110: warning: narrowing conversion of '(((int)y) + 1)' from 'int' to 'short int' inside { } [-Wnarrowing]
             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});
                                                                                                            ~~^~~
retro.cpp: At global scope:
retro.cpp:96:12: error: '::main' must return 'int'
 short main(){
            ^