Submission #38297

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38297	2018-01-03T14:03:33 Z	nibnalin	Retro (COCI17_retro)	C++14	24 / 100	500 ms	171128 KB

retro

#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 > 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)
{
	//cout << bool('(' < ')');
	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 < 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(\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;

		if(c != 0) printf("%c", A[cur.first][cur.second]);

		int dir = memoi[cur.first][cur.second][diff];
		cout << memoi[cur.first][cur.second][diff] << "\n";
		cur = {cur.first+xx[dir], cur.second+yy[dir]};
		diff += c;
	}
	printf("\n");*/
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:81:17: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  pair<int, int> cur = {r-1, start};
                 ^
retro.cpp:63: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:80:39: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pair<int, int> res = DP(r-1, start, 0);
                                       ^

Subtask #1

24.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	46 ms	170996 KB	Partially correct
2	Partially correct	36 ms	170996 KB	Partially correct
3	Partially correct	29 ms	170996 KB	Partially correct
4	Partially correct	66 ms	170996 KB	Partially correct
5	Partially correct	46 ms	170996 KB	Partially correct
6	Partially correct	33 ms	170996 KB	Partially correct
7	Partially correct	23 ms	170996 KB	Partially correct
8	Partially correct	39 ms	170996 KB	Partially correct
9	Partially correct	33 ms	170996 KB	Partially correct
10	Partially correct	33 ms	170996 KB	Partially correct
11	Execution timed out	500 ms	171128 KB	Execution timed out
12	Execution timed out	500 ms	171128 KB	Execution timed out
13	Partially correct	276 ms	171128 KB	Partially correct
14	Partially correct	266 ms	171128 KB	Partially correct
15	Execution timed out	500 ms	171128 KB	Execution timed out
16	Execution timed out	500 ms	171128 KB	Execution timed out
17	Execution timed out	500 ms	171128 KB	Execution timed out
18	Execution timed out	500 ms	171128 KB	Execution timed out
19	Execution timed out	500 ms	171128 KB	Execution timed out
20	Execution timed out	500 ms	171128 KB	Execution timed out