Submission #81408

#TimeUsernameProblemLanguageResultExecution timeMemory
81408luckyboyRetro (COCI17_retro)C++14
20 / 100
1103 ms525312 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 "" 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; char c[maxn][maxn]; pair <bitset <maxn>,int> dp[maxn][maxn][maxn]; bool Greater(bitset <maxn> x,bitset <maxn> y) { FORD(i,maxn-1,0) if (x[i] != y[i]) return x[i] > y[i]; return 0; } 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].S = -maxc; FOR(i,1,m) { cin >> c[1][i]; if (c[1][i] == '.') dp[1][i][0].S = 0; else if (c[1][i] == ')') dp[1][i][1].S = 1; } FOR(i,2,n) FOR(j,1,m) { cin >> c[i][j]; if (c[i][j] == '*') { dp[i][j][0].S = 0; continue; } if (c[i][j] == '.' || c[i][j] == 'M') { FOR(k,0,n) { FOR(dis,-1,1) { int x = j + dis; if (x < 1 || x > m) continue; if (dp[i][j][k].S < dp[i-1][x][k].S) { dp[i][j][k] = dp[i-1][x][k]; } else if (dp[i][j][k].S == dp[i-1][x][k].S && Greater(dp[i-1][x][k].F,dp[i][j][k].F)) { dp[i][j][k].F = dp[i-1][x][k].F; } } } continue; } if (c[i][j] == ')') { FOR(k,1,n) { FOR(dis,-1,1) { int x = j + dis; if (x < 1 || x > m || dp[i-1][x][k-1].S < 0) continue; if (dp[i][j][k].S < dp[i-1][x][k-1].S + 1) { dp[i][j][k] = dp[i-1][x][k-1]; ++dp[i][j][k].S; dp[i][j][k].F.set(dp[i][j][k].S,0); } else if (dp[i][j][k].S == dp[i-1][x][k-1].S + 1 && Greater(dp[i-1][x][k-1].F,dp[i][j][k].F)) { dp[i][j][k].F = dp[i-1][x][k].F; } } } continue; } FOR(k,0,n-1) { FOR(dis,-1,1) { int x = j + dis; if (x < 1 || x > m || dp[i-1][x][k+1].S < 0) continue; if (dp[i][j][k].S < dp[i-1][x][k+1].S + 1) { dp[i][j][k] = dp[i-1][x][k+1]; ++dp[i][j][k].S; dp[i][j][k].F.set(dp[i][j][k].S,1); } else if (dp[i][j][k].S == dp[i-1][x][k+1].S + 1) { bitset <maxn> temp = dp[i-1][x][k+1].S; temp.set(dp[i][j][k].S,1); if (Greater(temp,dp[i][j][k].F)) dp[i][j][k].F = temp; } } } } int pos; FOR(i,1,m) if (c[n][i] == 'M') { pos = i; break; } cout << dp[n][pos][0].S << '\n'; FORD(i,dp[n][pos][0].S,1) if(dp[n][pos][0].F[i]) cout << '('; else cout << ')'; return 0; }

Compilation message (stderr)

retro.cpp: In function 'int main()':
retro.cpp:115:9: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int pos;
         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...