Submission #879752

# Submission time Handle Problem Language Result Execution time Memory
879752 2023-11-28T04:03:47 Z 1075508020060209tc Retro (COCI17_retro) C++14
22 / 100
148 ms 216272 KB
//#pragma gcc optimize("O2")
#include <bits/stdc++.h>
//#include<complex>
using namespace std;
#define int long long
int n;int m;
string gr[510];
int dp[302][302][302];
 
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>gr[i];
    gr[i]="*"+gr[i]+"*";
}
for(int i=0;i<=n;i++){
    for(int j=0;j<=m;j++){
        for(int k=0;k<=n;k++){
            dp[i][j][k]=-1e9;
        }
    }
}
for(int i=1;i<=m;i++){
    if(gr[1][i]==')'){
        dp[1][i][1]=0;
    }
    if(gr[1][i]=='.'){
        dp[1][i][0]=0;
    }
}
for(int i=2;i<=n;i++){
    for(int j=1;j<=m;j++){
        for(int k=0;k<=i;k++){
            if(gr[i][j]=='*'){continue;}
            if(gr[i][j]=='.'||gr[i][j]=='M'){
                dp[i][j][k]=max({dp[i][j][k],dp[i-1][j][k],dp[i-1][j-1][k],dp[i-1][j+1][k]});
            }
            if(gr[i][j]==')'&&k>=1){
                dp[i][j][k]=max({dp[i][j][k],dp[i-1][j][k-1],dp[i-1][j-1][k-1],dp[i-1][j+1][k-1]});
            }
            if(gr[i][j]=='('){
                dp[i][j][k]=max({dp[i][j][k],1+dp[i-1][j][k+1],1+dp[i-1][j-1][k+1],1+dp[i-1][j+1][k+1]});
            }
        }
    }
}
int nw;
for(int i=1;i<=m;i++){
    if(gr[n][i]=='M'){
        nw=i;
    }
}
cout<<max(0ll,dp[n][nw][0])*2<<"\n";
cout<<"()\n";return 0;
for(int k=0;k<=3;k++){
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<dp[i][j][k]<<" ";
    }cout<<endl;
}cout<<endl;
}
 
 
}
# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 8796 KB Partially correct
2 Incorrect 2 ms 12636 KB Output isn't correct
3 Partially correct 2 ms 12636 KB Partially correct
4 Partially correct 2 ms 14684 KB Partially correct
5 Partially correct 2 ms 14940 KB Partially correct
6 Partially correct 11 ms 39260 KB Partially correct
7 Incorrect 9 ms 42588 KB Output isn't correct
8 Incorrect 6 ms 39772 KB Output isn't correct
9 Incorrect 10 ms 44952 KB Output isn't correct
10 Partially correct 13 ms 48632 KB Partially correct
11 Partially correct 148 ms 203764 KB Partially correct
12 Partially correct 127 ms 203648 KB Partially correct
13 Incorrect 58 ms 111288 KB Output isn't correct
14 Incorrect 59 ms 114804 KB Output isn't correct
15 Incorrect 141 ms 216272 KB Output isn't correct
16 Incorrect 138 ms 215972 KB Output isn't correct
17 Incorrect 110 ms 187984 KB Output isn't correct
18 Partially correct 108 ms 187772 KB Partially correct
19 Partially correct 133 ms 216248 KB Partially correct
20 Partially correct 125 ms 216144 KB Partially correct