Submission #163812

#	Time	Username	Problem	Language	Result	Execution time	Memory
163812		Ort	Retro (COCI17_retro)	C++11	40 / 100	194 ms	56984 KiB

retro

#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++)
			if(mat[i][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/2+1;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] << "\n()";
	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] = '*';
}

• Subtask 1: 40 / 100