Submission #1144850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144850		nuutsnoynton	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	303 ms	59284 KiB

dango_maker

#include<bits/stdc++.h>

using namespace std;
using ll = int;
using pll = pair< ll, ll >;
ll a[6005][6005], dp[12002][3] = {0};
int main() {
	ll n, m, r, x, hvt_cnt, bos_cnt, y, i, j, ans, t;

	cin >> n >> m;
	
	string str[n + 2];
	
	for (i = 1; i <= n; i ++) {
		cin >> str[i];
		for (j = 0; j < m; j ++) {
			if ( str[i][j] == 'R') a[i][j + 1] = 1;
			if ( str[i][j] == 'G') a[i][j + 1] = 2;
			if ( str[i][j] == 'W') a[i][j + 1] = 3;
		}
		
	}
	ans = 0;
	for (i = 2; i <= n + m; i ++) {
		x = i - 1;
		y = 1;
		r =1;
		dp[r][0] = dp[r][1] = dp[r][2] = 0;
		if ( a[x][y - 1] == 1 && a[x][y] == 2 && a[x][y + 1] == 3) dp[r][1] = 1;
		if ( a[x - 1][y] == 1 && a[x][y] == 2 && a[x + 1][y] == 3) dp[r][2] = 1;
		x --;
		y ++;	
		r ++;	
		while ( x >= 1 && y <= m) {
			dp[r][0] = dp[r][1] = dp[r][2] =  max({dp[r - 1][0], dp[r - 1][1], dp[r - 1][2]});
			
			if ( a[x][y - 1] == 1 && a[x][y] == 2 && a[x][y + 1] == 3) dp[r][1] = max(dp[r][1], max(dp[r - 1][1], dp[r- 1][0]) + 1);
			if ( a[x - 1][y] == 1 && a[x][y] == 2 && a[x + 1][y] == 3) dp[r][2] = max(dp[r][2], max(dp[r - 1][2], dp[r- 1][0]) + 1);
			x --;
			y ++;
			r ++;
		}
		r --;
		ans += max({dp[r][0], dp[r][1], dp[r][2]});
	}
	cout << ans << endl;
	
	
	
}

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