oj.uz

Submission #879726

# Submission time Handle Problem Language Result Execution time Memory
879726 2023-11-28T02:28:05 Z 1075508020060209tc Retro (COCI17_retro) C++14
22 / 100
 70 ms 108056 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]=-1e7;
        }
    }
}
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(0,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;
}


}

Subtask #1
22.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 KB Partially correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Partially correct 1 ms 6488 KB Partially correct
4 Partially correct 1 ms 6492 KB Partially correct
5 Partially correct 1 ms 6492 KB Partially correct
6 Partially correct 4 ms 24924 KB Partially correct
7 Incorrect 4 ms 29276 KB Output isn't correct
8 Incorrect 5 ms 35164 KB Output isn't correct
9 Incorrect 6 ms 37468 KB Output isn't correct
10 Partially correct 6 ms 37468 KB Partially correct
11 Partially correct 55 ms 101204 KB Partially correct
12 Partially correct 53 ms 101208 KB Partially correct
13 Incorrect 31 ms 107352 KB Output isn't correct
14 Incorrect 29 ms 107356 KB Output isn't correct
15 Incorrect 59 ms 107608 KB Output isn't correct
16 Incorrect 58 ms 107604 KB Output isn't correct
17 Incorrect 52 ms 107864 KB Output isn't correct
18 Partially correct 50 ms 107864 KB Partially correct
19 Partially correct 60 ms 107896 KB Partially correct
20 Partially correct 70 ms 108056 KB Partially correct