Submission #532554

#	Time	Username	Problem	Language	Result	Execution time	Memory
532554		rk42745417	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	4 ms	2764 KiB

dango_maker

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

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using uint = uint32_t;
using ull = uint64_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
const ll LINF = ll(4e18) + ll(2e15);
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int N = 11;
int mpow[N], dp[N][59049], n, m;
string arr[N];

void go(int x, int y, int cur, int nxt_bit, int v) {
	if(cur == m) {
		dp[x + 1][nxt_bit] = max(dp[x + 1][nxt_bit], v);
		return;
	}
	if(arr[x][cur] == 'R') {
		go(x, y, cur + 1, nxt_bit + mpow[cur], v);
		if(cur + 2 < m && arr[x][cur + 1] == 'G' && arr[x][cur + 2] == 'W')
			go(x, y, cur + 3, nxt_bit, v + 1);
	}
	if(arr[x][cur] == 'G') {
		int r = y / mpow[cur] % 3;
		if(r == 1)
			go(x, y, cur + 1, nxt_bit + 2 * mpow[cur], v);
		else
			go(x, y, cur + 1, nxt_bit, v);
	}
	if(arr[x][cur] == 'W') {
		int r = y / mpow[cur] % 3;
		go(x, y, cur + 1, nxt_bit, v + (r == 2));
	}
}

signed main() {
	cin >> n >> m;
	mpow[0] = 1;
	for(int i = 1; i <= m; i++)
		mpow[i] = mpow[i - 1] * 3;
	for(int i = 0; i < n; i++)
		cin >> arr[i];

	for(int i = 0; i <= n; i++)
		for(int j = 0; j < mpow[m]; j++)
			dp[i][j] = -INF;

	{
		int r = 0;
		for(int j = 0; j < m; j++)
			if(arr[0][j] == 'R')
				r += mpow[j];
		dp[0][r] = 0;
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < mpow[m]; j++)
			if(dp[i][j] != -INF)
				go(i, j, 0, 0, dp[i][j]);
	int ans = 0;
	for(int j = 0; j < mpow[m]; j++)
		ans = max(ans, dp[n][j]);
	cout << ans << '\n';
}

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