Submission #81243

#TimeUsernameProblemLanguageResultExecution timeMemory
81243luckyboyRetro (COCI17_retro)C++14
20 / 100
314 ms218216 KiB
/**Lucky Boy**/ #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) #define FORD(i, a, b) for (int i = (a); i >= (b); --i) #define pb push_back #define mp make_pair #define F first #define S second #define maxc 1000000007 #define maxn 305 #define maxm 500005 #define pii pair <int,int> #define Task "Retro" template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');} template <typename T> inline void writeln(T x){write(x);putchar('\n');} using namespace std; int n,m,tr[maxn][maxn][maxn],dp[maxn][maxn][maxn]; char c[maxn][maxn]; vector <char> res; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //freopen(Task".inp", "r",stdin); //freopen(Task".out", "w",stdout); cin >> n >> m; FOR(i,1,n) FOR(j,1,m) FOR(k,0,n) dp[i][j][k] = -maxc; FOR(i,1,n) FOR(j,1,m) { cin >> c[i][j]; if (c[i][j] == 'M') dp[i][j][0] = 0; } FORD(i,n-1,1) FOR(j,1,m) { if (c[i][j] == '*') continue; if (c[i][j] == '.') { FOR(k,0,n) { FOR(dis,-1,1) { int x = j + dis; if (x < 0 || x > m) continue; if (dp[i][j][k] < dp[i+1][x][k]) { dp[i][j][k] = dp[i+1][x][k]; tr[i][j][k] = x; } } } continue; } if (c[i][j] == '(') { FOR(k,1,n) { FOR(dis,-1,1) { int x = j + dis; if (x < 0 || x > m) continue; if (dp[i][j][k] < dp[i+1][x][k-1] + 1) { dp[i][j][k] = dp[i+1][x][k-1] + 1; tr[i][j][k] = x; } } } continue; } FOR(k,0,n - 1) { FOR(dis,-1,1) { int x = j + dis; if (x < 0 || x > m) continue; if (dp[i][j][k] < dp[i+1][x][k+1] + 1) { dp[i][j][k] = dp[i+1][x][k+1] + 1; tr[i][j][k] = x; } } } } int ans = -maxc,u,v; FOR(i,1,n) FOR(j,1,n) if (ans < dp[i][j][0]) { ans = dp[i][j][0]; u = i,v = j; } cout << ans << '\n'; int ww = 0; while (u <= n) { char temp = c[u][v]; v = tr[u][v][ww]; res.pb(temp); ++u; if (temp == '(') --ww; else if (temp == ')') ++ww; } reverse(res.begin(),res.end()); for (char c : res) if (c == '(' || c == ')') cout << c; return 0; }

Compilation message (stderr)

retro.cpp: In function 'int main()':
retro.cpp:102:11: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
         v = tr[u][v][ww];
         ~~^~~~~~~~~~~~~~
retro.cpp:104:9: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ++u;
         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...