Submission #163808

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
163808	2019-11-15T12:55:25 Z	Ort	Retro (COCI17_retro)	C++11	20 / 100	500 ms	56968 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++)
			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] << "\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

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	49 ms	56824 KB	Partially correct
2	Partially correct	49 ms	56696 KB	Partially correct
3	Partially correct	49 ms	56824 KB	Partially correct
4	Partially correct	49 ms	56824 KB	Partially correct
5	Partially correct	49 ms	56824 KB	Partially correct
6	Partially correct	57 ms	56756 KB	Partially correct
7	Partially correct	54 ms	56824 KB	Partially correct
8	Partially correct	55 ms	56824 KB	Partially correct
9	Partially correct	54 ms	56824 KB	Partially correct
10	Partially correct	56 ms	56824 KB	Partially correct
11	Incorrect	467 ms	56968 KB	Output isn't correct
12	Incorrect	399 ms	56948 KB	Output isn't correct
13	Incorrect	235 ms	56824 KB	Output isn't correct
14	Incorrect	209 ms	56952 KB	Output isn't correct
15	Execution timed out	556 ms	56880 KB	Time limit exceeded
16	Incorrect	496 ms	56952 KB	Output isn't correct
17	Incorrect	446 ms	56952 KB	Output isn't correct
18	Incorrect	445 ms	56876 KB	Output isn't correct
19	Execution timed out	673 ms	56876 KB	Time limit exceeded
20	Incorrect	494 ms	56952 KB	Output isn't correct