Submission #879726

#	Time	Username	Problem	Language	Result	Execution time	Memory
879726		1075508020060209tc	Retro (COCI17_retro)	C++14	22 / 100	70 ms	108056 KiB

retro

//#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 / 100