Submission #1284620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284620		Jawad_Akbar_JJ	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	385 ms	9632 KiB

dango_maker

#include <iostream>

using namespace std;
const int N = 3050;
char a[N][N];
int n, m, dp[N][3], Ans;

int poss(int i, int j, int tp){
	if (tp == 0)
		return 0;
	
	int i1, i2, j1, j2;
	if (tp == 1)
		i1 = i - 1, i2 = i + 1, j1 = j2 = j;
	else
		i1 = i2 = i, j1 = j - 1, j2 = j + 1;

	if (i1 < 1 or j1 < 1 or i2 > n or j2 > m)
		return 0;
	if (i1 == i2)
		return (a[i1][j1] == 'R' and a[i1][j1+1] == 'G' and a[i1][j1+2] == 'W');
	return (a[i1][j1] == 'R' and a[i1+1][j1] == 'G' and a[i1+2][j1] == 'W');
}

void solve(int i, int j){
	if (i > n or j < 1 or a[i][j] != 'G'){
		Ans += max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]));
		return;
	}
	dp[i][0] = max(dp[i-1][1], max(dp[i-1][0], dp[i-1][2]));
	dp[i][1] = max(dp[i-1][1], dp[i-1][0]) + poss(i, j, 1);
	dp[i][2] = max(dp[i-1][2], dp[i-1][0]) + poss(i, j, 2);

	solve(i+1, j-1);

	dp[i][0] = dp[i][1] = dp[i][2] = 0;
}

int main(){
	cin>>n>>m;

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++)
			cin>>a[i][j];
	}

	for (int i=1;i<=n;i++){
		for (int j=m;j>=1;j--){
			if (a[i][j] != 'G' or (i > 1 and j < m and a[i-1][j+1] == 'G'))
				continue;
			solve(i, j);
		}
	}

	cout<<Ans<<'\n';
}

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