Submission #305261

#	Time	Username	Problem	Language	Result	Execution time	Memory
305261		shivensinha4	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	415 ms	71176 KiB

dango_maker

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m; cin >> n >> m;
	vector<vi> mat(n, vi(m));
	for_(i, 0, n) for_(j, 0, m) {
		char c; cin >> c;
		if (c == 'R') mat[i][j] = 0;
		else if (c == 'G') mat[i][j] = 1;
		else mat[i][j] = 2;
	}
	
	//cout << "done" << endl;
	
	vector<vi> dir(n, vi(m)); // 0 -> nothing, 1 -> vertical possible, 2 -> horizontal possible
	for_(i, 0, n) for_(j, 0, m) if (mat[i][j] == 0) {
		if (i < n-2 and mat[i+1][j] == 1 and mat[i+2][j] == 2) dir[i][j] += 1;
		if (j < m-2 and mat[i][j+1] == 1 and mat[i][j+2] == 2) dir[i][j] += 2;
	}
	
	ll ans = 0;
	for_(i, 0, n) for_(j, 0, m) {
		if (i > 0 and j != m-1) {
			j = m-2;
			continue;
		}
		vi prev(3), curr(3);
		for (int r = min(i+j, n-1); r >= i; r--) {
			int c = i+j-r;
			int hor = !!(dir[r][c]&2), ver = dir[r][c]&1;
			assert(c >= 0);
			
			curr[0] = prev[0] + hor;
			if (ver) curr[0] = max(curr[0], prev[1] + 1);
			
			curr[1] = prev[2];
			if (ver) curr[1] = max(curr[1], prev[1] + 1);
			
			curr[2] = prev[0];
			if (ver) curr[2] = max(curr[2], prev[1] + 1);
			
			swap(curr, prev);
		}
		
		ans += prev[0];
	}
	
	cout << ans << endl;

	return 0;
}

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