oj.uz

답안 #163812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163812 2019-11-15T12:59:12 Z Ort Retro (COCI17_retro) C++11
40 / 100
 194 ms 56984 KB 
#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

# 결과 실행 시간 메모리 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