Submission #675433

#	Time	Username	Problem	Language	Result	Execution time	Memory
675433		AmirAli_H1	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	766 ms	234372 KiB

dango_maker

// In the name of Allah

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

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, m;
const int maxn = 3e3 + 4;
int a[maxn][maxn];
bool M[maxn][maxn][2];
int dp[maxn][maxn][3];
set<pii> res;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			if (s[j] == 'R') a[i][j] = 0;
			else if (s[j] == 'G') a[i][j] = 1;
			else a[i][j] = 2;
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m - 2; j++) {
			if (a[i][j] == 0 && a[i][j + 1] == 1 && a[i][j + 2] == 2) {
				M[i][j + 1][0] = 1;
			}
		}
	}
	
	for (int i = 0; i < n - 2; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 0 && a[i + 1][j] == 1 && a[i + 2][j] == 2) {
				M[i + 1][j][1] = 1;
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = m - 1; j >= 0; j--) {
			if (!(M[i][j][0] || M[i][j][1])) continue;
			
			dp[i][j][1] = M[i][j][0]; dp[i][j][2] = M[i][j][1];
			res.insert(Mp(i, j));
			
			int i1 = i - 1, j1 = j + 1;
			if (i1 >= 0 && j1 < m && (M[i1][j1][0] || M[i1][j1][1])) {
				dp[i][j][0] = max(dp[i1][j1][0], max(dp[i1][j1][1], dp[i1][j1][2]));
				if (M[i][j][0]) {
					dp[i][j][1] += max(dp[i1][j1][0], dp[i1][j1][1]);
				}
				if (M[i][j][1]) {
					dp[i][j][2] += max(dp[i1][j1][0], dp[i1][j1][2]);
				}
				res.erase(Mp(i1, j1));
			}
		}
	}
	
	ll output = 0;
	for (auto f : res) {
		auto [i, j] = f;
		output += max(dp[i][j][0], max(dp[i][j][1], dp[i][j][2]));
	}
	cout << output << endl;
	
	return 0;
}

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