답안 #38284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38284 2018-01-03T13:29:52 Z nibnalin Retro (COCI17_retro) C++14
0 / 100
456 ms 171128 KB
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 305, maxl = 155, inf = int(1e5)+5;

const int xx[3] = {-1, -1, -1};
const int yy[3] = {-1, 0, 1};

int r, s, memoi[maxn][maxn][maxl];
pair<int, int> memo[maxn][maxn][maxl];
string A[maxn];

inline bool valid(int x, int y) { return (x >= -1 && y >= 0 && x < r && y < s); }

pair<int, int> DP(int x, int y, int diff)
{
	if(x == -1) return {(diff?-inf:0), inf};
	else if(diff < 0 || diff > maxl) return {-inf, inf};
	if(A[x][y] == '*') return {(diff?-inf:0), inf};
	else if(memo[x][y][diff].first != -1) return memo[x][y][diff];
	else if(A[x][y] == '(' || A[x][y] == ')')
	{
		int c;
		pair<int, int> res = {-inf, inf};
		if(A[x][y] == '(') c = 1;
		else c = -1;
		for(int i = 0;i < 3;i++)
		{
			int u = x+xx[i], v = y+yy[i];
			if(valid(u, v))
			{
				pair<int, int> tmp = DP(u, v, diff+c);
				if(tmp.first > res.first) res = tmp, memoi[x][y][diff] = i;
				else if(tmp.first == res.first && tmp.second < res.second) res = tmp, memoi[x][y][diff] = i;
			}
		}
		//cout << x << " " << y << " " << diff << " " << c << " " << res.first << " " << res.second << "\n";
		return memo[x][y][diff] = {res.first+1, A[x][y]};
	}
	else
	{
		pair<int, int> res = {-inf, inf};
		for(int i = 0;i < 3;i++)
		{
			int u = x+xx[i], v = y+yy[i];
			if(valid(u, v))
			{
				pair<int, int> tmp = DP(u, v, diff);
				if(tmp.first > res.first) res = tmp, memoi[x][y][diff] = i;
				else if(tmp.first == res.first && tmp.second < res.second) res = tmp, memoi[x][y][diff] = i;
			}
		}
		//cout << x << " " << y << " " << diff << " " << res.first << " " << res.second << "\n";
		return memo[x][y][diff] = res;
	}
}

int main(void)
{
	scanf("%d%d", &r, &s);
	for(int i = 0;i < r;i++) cin >> A[i];

	for(int i = 0;i < maxn;i++)
	{
		for(int j = 0;j < maxl;j++)
		{
			for(int k = 0;k < maxl;k++) memo[i][j][k] = {-1, -1}, memoi[i][j][k] = -1;
		}
	}

	int start;
	for(int i = 0;i < s;i++)
	{
		if(A[r-1][i] == 'M') start = i;
	}

	pair<int, int> res = DP(r-1, start, 0);
	pair<int, int> cur = {r-1, start};
	int diff = 0;

	printf("%d\n", res.first);
	/*while(cur.first != -1 && A[cur.first][cur.second] != '*')
	{
		int c = 0;
		if(A[cur.first][cur.second] == '(') c = 1;
		else if(A[cur.first][cur.second] == ')') c = -1;

		int dir = memoi[cur.first][cur.second][diff];
		pair<int, int> nex = {cur.first+xx[dir], cur.second+yy[dir]};
		if(c != 0) cout << A[cur.first][cur.second];
		cur = nex;
		diff += c;
	}*/
	cout << "\n";
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:80:17: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  pair<int, int> cur = {r-1, start};
                 ^
retro.cpp:81:6: warning: unused variable 'diff' [-Wunused-variable]
  int diff = 0;
      ^
retro.cpp:62:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &r, &s);
                       ^
retro.cpp:73:6: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int start;
      ^
# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 170996 KB Unexpected end of file - token expected
2 Incorrect 9 ms 170996 KB Unexpected end of file - token expected
3 Incorrect 16 ms 170996 KB Unexpected end of file - token expected
4 Incorrect 23 ms 170996 KB Unexpected end of file - token expected
5 Incorrect 23 ms 170996 KB Unexpected end of file - token expected
6 Incorrect 26 ms 170996 KB Unexpected end of file - token expected
7 Incorrect 6 ms 170996 KB Unexpected end of file - token expected
8 Incorrect 13 ms 170996 KB Unexpected end of file - token expected
9 Incorrect 19 ms 170996 KB Unexpected end of file - token expected
10 Incorrect 43 ms 170996 KB Unexpected end of file - token expected
11 Incorrect 299 ms 171128 KB Unexpected end of file - token expected
12 Incorrect 276 ms 171128 KB Unexpected end of file - token expected
13 Incorrect 316 ms 171128 KB Unexpected end of file - token expected
14 Incorrect 296 ms 171128 KB Unexpected end of file - token expected
15 Incorrect 9 ms 171128 KB Integer 0 violates the range [1, 100000]
16 Incorrect 23 ms 171128 KB Integer 0 violates the range [1, 100000]
17 Incorrect 456 ms 171128 KB Unexpected end of file - token expected
18 Incorrect 336 ms 171128 KB Unexpected end of file - token expected
19 Incorrect 376 ms 171128 KB Unexpected end of file - token expected
20 Incorrect 289 ms 171128 KB Unexpected end of file - token expected