Submission #163807

#TimeUsernameProblemLanguageResultExecution timeMemory
163807OrtRetro (COCI17_retro)C++11
0 / 100
544 ms57080 KiB
#include<bits/stdc++.h> #define MAX 305 #define HMAX 155 #define inf 1000000 using namespace std; int n, m, sy, sx; int dx[3] = {-1, 0, 1}; int dy[3] = {1, 1, 1}; int dp[MAX][MAX][HMAX]; char mat[MAX][MAX]; bool inside(int y, int x) {return y>=0 && x>0 && y<=n && x<=m;} void input(); int main() { input(); memset(dp, -1, sizeof(dp)); for(int i=0;i<n;i++) for(int j=1;j<=m;j++) dp[i][j][0] = 0; for(int i=0;i<n;i++) for(int j=1;j<=m;j++) for(int k=0;k<n;k++) { if(dp[i][j][k]==-1) continue; for(int l=0;l<3;l++) { int y = i+dy[l]; int x = j+dx[l]; if(!inside(y,x)) continue; if(mat[y][x]==')') dp[y][x][k+1] = max(dp[y][x][k+1], dp[i][j][k]+1); if(mat[y][x]=='(' && k>0) dp[y][x][k-1] = max(dp[y][x][k-1], dp[i][j][k]+1); if(mat[y][x]=='.' || mat[y][x]=='M') dp[y][x][k] = max(dp[y][x][k], dp[i][j][k]); } } cout << dp[sy][sx][0] << "()"; return 0; } void input() { cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin >> mat[i][j]; if(mat[i][j]=='M') sy = i, sx = j; } for(int i=1;i<=m;i++) mat[0][i] = '*'; }
#Verdict Execution timeMemoryGrader output
Fetching results...