Submission #305258

#	Time	Username	Problem	Language	Result	Execution time	Memory
305258		shivensinha4	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	422 ms	71544 KiB

dango_maker

#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) 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);
			
			//for_(k, 0, 3) curr[i] += prev[i];
			//for (int k: curr) cout << k << " ";
			//cout << endl;
			swap(curr, prev);
		}
		
		ans += prev[0];
		//cout << "got value " << prev[0] << " for the diagonal ending on " << i << " " << j << endl;
		//assert(curr[0] == *max_element(curr.begin(), curr.end()));
	}
	
	cout << ans << endl;

	return 0;
}

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