Submission #38280

#	Time	Username	Problem	Language	Result	Execution time	Memory
38280		nibnalin	Retro (COCI17_retro)	C++14	44 / 100	500 ms	334648 KiB

retro

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

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

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

int r, s, memoi[maxn][maxn][maxn];
pair<int, int> memo[maxn][maxn][maxn];
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 > r) 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 < maxn;j++)
		{
			for(int k = 0;k < maxn;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 (stderr)

retro.cpp: In function 'int main()':
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:84:50: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while(cur.first != -1 && A[cur.first][cur.second] != '*')
                                                  ^

• Subtask 1: 44 / 100