Submission #163812

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
163812	2019-11-15T12:59:12 Z	Ort	Retro (COCI17_retro)	C++11	40 / 100	194 ms	56984 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	50 ms	56696 KB	Partially correct
2	Partially correct	50 ms	56828 KB	Partially correct
3	Partially correct	50 ms	56696 KB	Partially correct
4	Partially correct	49 ms	56704 KB	Partially correct
5	Partially correct	50 ms	56824 KB	Partially correct
6	Partially correct	59 ms	56696 KB	Partially correct
7	Partially correct	53 ms	56696 KB	Partially correct
8	Partially correct	51 ms	56828 KB	Partially correct
9	Partially correct	54 ms	56984 KB	Partially correct
10	Partially correct	55 ms	56796 KB	Partially correct
11	Partially correct	166 ms	56876 KB	Partially correct
12	Partially correct	151 ms	56952 KB	Partially correct
13	Partially correct	100 ms	56916 KB	Partially correct
14	Partially correct	108 ms	56972 KB	Partially correct
15	Partially correct	194 ms	56824 KB	Partially correct
16	Partially correct	169 ms	56920 KB	Partially correct
17	Partially correct	158 ms	56800 KB	Partially correct
18	Partially correct	138 ms	56824 KB	Partially correct
19	Partially correct	192 ms	56916 KB	Partially correct
20	Partially correct	165 ms	56904 KB	Partially correct