Submission #1255092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255092		g4yuhg	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	307 ms	9516 KiB

dango_maker

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll> 
#define fi first
#define se second
#define TASK "mansion"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 3015
#define endl '\n'
using namespace std;
 
bool ghuy4g;

ll n, m, f[N][3], fh, lh, tong, ans;
char a[N][N];

// 1 la ngang 
// 2 la doc

ll dp(ll i, ll j) { // i la hang hien tai
	//cout << i << " " << j << endl;
	if (tong - i <= 0 || i > n) {
		return 0;
	}
	if (f[i][j] != -1) {
		return f[i][j];
	}
	// i la hang, vay cot la tong - i;
	ll cot = tong - i;
	ll xet = 0;
	if (j == 0) {
		xet = max({dp(i + 1, 0), dp(i + 1, 1), dp(i + 1, 2)});
	}
	else if (j == 1) {
		if (a[i][cot] == 'G' && a[i][cot + 1] == 'W' && a[i][cot - 1] == 'R') {
			xet = 1 + max(dp(i + 1, 1), dp(i + 1, 0));
		}
	}
	else if (j == 2) {
		if (a[i][cot] == 'G' && a[i + 1][cot] == 'W' && a[i - 1][cot] == 'R') {
			xet = 1 + max(dp(i + 1, 2), dp(i + 1, 0));
		}
	}
	f[i][j] = xet;
	return xet;
}

void solve() { // cac o cung tong
	memset(f, -1, sizeof(f));
	ll fh = max(tong - m, 1);
	ll xet = max({dp(fh, 0), dp(fh, 1), dp(fh, 2)});
	ans += xet;
}
 
bool klinh;
 
signed main(void) {
	faster;
	
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			cin >> a[i][j];
		}
	}
	
	for (int id = n + m; id >= 1; id --) {
		tong = id;
		solve();
	}
	
	cout << ans;
		
	cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
	return 0;
}

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