Submission #40087

# Submission time Handle Problem Language Result Execution time Memory
40087 2018-01-26T15:33:01 Z Hebisuke Retro (COCI17_retro) C++14
49 / 100
371 ms 335268 KB
#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

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 time Memory Grader output
1 Partially correct 0 ms 334516 KB Partially correct
2 Correct 1 ms 334516 KB Output is correct
3 Partially correct 0 ms 334516 KB Partially correct
4 Correct 1 ms 334516 KB Output is correct
5 Correct 0 ms 334516 KB Output is correct
6 Partially correct 10 ms 334648 KB Partially correct
7 Partially correct 6 ms 334516 KB Partially correct
8 Partially correct 11 ms 334516 KB Partially correct
9 Partially correct 14 ms 334516 KB Partially correct
10 Partially correct 18 ms 334648 KB Partially correct
11 Partially correct 276 ms 335032 KB Partially correct
12 Partially correct 262 ms 335036 KB Partially correct
13 Partially correct 149 ms 334780 KB Partially correct
14 Partially correct 132 ms 334648 KB Partially correct
15 Partially correct 371 ms 335268 KB Partially correct
16 Partially correct 325 ms 335128 KB Partially correct
17 Partially correct 297 ms 335144 KB Partially correct
18 Partially correct 238 ms 334908 KB Partially correct
19 Partially correct 359 ms 335232 KB Partially correct
20 Partially correct 301 ms 335096 KB Partially correct