Submission #40086

#TimeUsernameProblemLanguageResultExecution timeMemory
40086HebisukeRetro (COCI17_retro)C++14
46 / 100
394 ms335268 KiB
#include "stdio.h" #include "queue" #include "algorithm" #include "stack" using namespace std; queue<pair<int,pair<int, int> > > q; int dp[305][305][305],s,r,x,y; char tb[305][305]; pair<int, int > p[305][305][305]; stack<char> st; main() { scanf("%d %d",&r,&s); for(int i=0;i<r;i++) scanf("%s",tb[i]); for(int i=0;i<r;i++) for(int j=0;j<s;j++){ for(int k=0;k<r;k++) {dp[i][j][k]=-1;p[i][j][k]=make_pair(j,k);} } for(int i=0;i<s;i++) if(tb[r-1][i]=='M') {q.push(make_pair(r-1,make_pair(i,0)));dp[r-1][i][0]=0; break;} while(!q.empty()) { int rr=q.front().first, cc=q.front().second.first , f=q.front().second.second; q.pop(); //printf("%d %d %d\n",rr,cc,f); if(rr==0) continue; if(cc>0) { char temp = tb[rr-1][cc-1]; if(temp=='(') { if(dp[rr-1][cc-1][f+1]<=dp[rr][cc][f]) { dp[rr-1][cc-1][f+1]=dp[rr][cc][f]; p[rr-1][cc-1][f+1]=make_pair(cc,f); } q.push(make_pair(rr-1,make_pair(cc-1,f+1))); } else if(temp==')') { if(f>=1){ if(dp[rr-1][cc-1][f-1]<dp[rr][cc][f]+2) { dp[rr-1][cc-1][f-1]=dp[rr][cc][f]+2; p[rr-1][cc-1][f-1]=make_pair(cc,f); } q.push(make_pair(rr-1,make_pair(cc-1,f-1)));} } else { if(dp[rr-1][cc-1][f]<dp[rr][cc][f]) { dp[rr-1][cc-1][f]=dp[rr][cc][f]; p[rr-1][cc-1][f]=make_pair(cc,f); if(temp!='*') q.push(make_pair(rr-1,make_pair(cc-1,f))); } } } if(cc<s-1) { char temp = tb[rr-1][cc+1]; if(temp=='(') { if(dp[rr-1][cc+1][f+1]<=dp[rr][cc][f]) { dp[rr-1][cc+1][f+1]=dp[rr][cc][f]; p[rr-1][cc+1][f+1]=make_pair(cc,f); } q.push(make_pair(rr-1,make_pair(cc+1,f+1))); } else if(temp==')') { if(f>=1){ if(dp[rr-1][cc+1][f-1]<dp[rr][cc][f]+2) { dp[rr-1][cc+1][f-1]=dp[rr][cc][f]+2; p[rr-1][cc+1][f-1]=make_pair(cc,f); } q.push(make_pair(rr-1,make_pair(cc+1,f-1)));} } else { if(dp[rr-1][cc+1][f]<dp[rr][cc][f]) { dp[rr-1][cc+1][f]=dp[rr][cc][f]; p[rr-1][cc+1][f]=make_pair(cc,f); if(temp!='*') q.push(make_pair(rr-1,make_pair(cc+1,f))); } } } char temp = tb[rr-1][cc]; if(temp=='(') { if(dp[rr-1][cc][f+1]<=dp[rr][cc][f]) { dp[rr-1][cc][f+1]=dp[rr][cc][f]; p[rr-1][cc][f+1]=make_pair(cc,f); } q.push(make_pair(rr-1,make_pair(cc,f+1))); } else if(temp==')') { if(f>=1){ if(dp[rr-1][cc][f-1]<dp[rr][cc][f]+2) { dp[rr-1][cc][f-1]=dp[rr][cc][f]+2; p[rr-1][cc][f-1]=make_pair(cc,f); } q.push(make_pair(rr-1,make_pair(cc,f-1)));} } else { if(dp[rr-1][cc][f]<dp[rr][cc][f]) { dp[rr-1][cc][f]=dp[rr][cc][f]; p[rr-1][cc][f]=make_pair(cc,f); if(temp!='*') q.push(make_pair(rr-1,make_pair(cc,f))); } } } int ma=0; for(int i=0;i<r;i++) for(int j=0;j<s;j++) if(dp[i][j][0]>ma) {ma=dp[i][j][0];x=i;y=j;} int k=0; while(x!=r-1) { if(tb[x][y]=='('||tb[x][y]==')') { st.push(tb[x][y]); } int a = p[x][y][k].first, b= p[x][y][k].second; y=a; k=b; x++; } printf("%d\n",ma); while(!st.empty()) { printf("%c",st.top()); st.pop(); } }

Compilation message (stderr)

retro.cpp:12:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
retro.cpp: In function 'int main()':
retro.cpp:14:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&r,&s);
                         ^
retro.cpp:16:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",tb[i]);
                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...