Submission #470531

#	Time	Username	Problem	Language	Result	Execution time	Memory
470531		maomao90	Dango Maker (JOI18_dango_maker)	C++17	0 / 100	1 ms	384 KiB

dango_maker

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 3005

int n, m;
char s[MAXN][MAXN];
int dp[MAXN][MAXN][5];
int ans;

bool rgw(int i, int j, bool isc) {
	if (!isc) {
		if (j + 2 >= m) return 0;
		if (s[i][j] == 'R' && s[i][j + 1] == 'G' && s[i][j + 2] == 'W') {
			return 1;
		}
		return 0;
	} else {
		if (i + 2 >= n) return 0;
		if (s[i][j] == 'R' && s[i + 1][j] == 'G' && s[i + 2][j] == 'W') {
			return 1;
		}
		return 0;
	}
	assert(0);
}

int main() {
	scanf("%d%d", &n, &m);
	REP (i, 0, n) {
		scanf(" %s", s[i]);
	}
	int pi = 0, pj = 0;
	dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = max(rgw(0, 0, 0), rgw(0, 0, 1));
	REP (ij, 1, n + m - 1) {
		REP (i, 0, ij + 1) {
			int j = ij - i;
			if (i >= n || j >= m) continue;
			if (rgw(i, j, 0)) {
				dp[i][j][0] = dp[pi][pj][0] + 1;
			}
			if (rgw(i, j, 1)) {
				dp[i][j][2] = max(dp[pi][pj][0],
					   	max(dp[pi][pj][1], dp[pi][pj][2])) + 1;
			}
			if (i != 0) {
				REP (k, 0, 3) {
					mxto(dp[i][j][max(k - 1, 0)], dp[pi][pj][k]);
				}
			}
			if (j == 0) {
				int tmp = 0;
				REP (k, 0, 3) {
					mxto(tmp, dp[i][j][k]);
				}
				REP (k, 0, 3) {
					dp[i][j][k] = tmp;
				}
			}
			debug("%d %d\n", i, j);
			REP (k, 0, 3) {
				debug(" %d: %d\n", k, dp[i][j][k]);
				mxto(ans, dp[i][j][k]);
			}
			pi = i; pj = j;
		}
	}
	printf("%d\n", ans);
	return 0;
}

/*
3 4
RGWR
GRGG
RGWW

4 4
RGWR
GRRG
WGGW
WWWR

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
dango_maker.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf(" %s", s[i]);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67