Submission #40087

#	Time	Username	Problem	Language	Result	Execution time	Memory
40087		Hebisuke	Retro (COCI17_retro)	C++14	49 / 100	371 ms	335268 KiB

retro

#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);
                            }else if(dp[rr-1][cc-1][f-1]==dp[rr][cc][f]+2&&tb[rr][cc]==')')
                            {
                                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);
                            }
                            else if(dp[rr-1][cc+1][f-1]==dp[rr][cc][f]+2&&tb[rr][cc]==')')
                            {
                                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);
                            }
                            else if(dp[rr-1][cc][f-1]==dp[rr][cc][f]+2&&tb[rr][cc]==')')
                            {
                                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]);
                          ^

• Subtask 1: 49 / 100