Submission #871144

#	Time	Username	Problem	Language	Result	Execution time	Memory
871144		aaron_dcoder	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	432 ms	231004 KiB

dango_maker

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;

ll N,M;
vector<string> D;

bool inrange(pll pos) {
	return 0<=pos.e0 && pos.e0<M && 0<=pos.e1 && pos.e1<N;
}

bool canhskewer(pll pos) {
	if (!inrange({pos.e0-1,pos.e1}) || !inrange({pos.e0+1,pos.e1})) return false;

	return D[pos.e1][pos.e0-1]=='R' && D[pos.e1][pos.e0]=='G' && D[pos.e1][pos.e0+1]=='W';
}

bool canvskewer(pll pos) {
	if (!inrange({pos.e0,pos.e1-1}) || !inrange({pos.e0,pos.e1+1})) return false;
//dbgv(D[pos.e1][pos.e0]=='G');
	return D[pos.e1-1][pos.e0]=='R' && D[pos.e1][pos.e0]=='G' && D[pos.e1+1][pos.e0]=='W';
}


int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	cin >> N >> M;

	D.assign(N,"");
	for (ll i = 0; i < N; ++i)
	{
	 	cin >> D[i];
	 	assert(ll(D[i].size())==M);
	}

	vector<vector<ll>> dp_vert(N,vector<ll>(M));
	vector<vector<ll>> dp_horiz(N,vector<ll>(M));
	vector<vector<ll>> dp_no(N,vector<ll>(M));
dbgv(canvskewer({3,1}));

	ll outp=0;
	for (ll d = 0; d < (M+N-1); ++d)
	{
		pll pos;
		if (d<M) 
		{
			pos = {d,0};
		}
		else {
			pos = {M-1,d-M+1};
		}

		dp_vert[pos.e1][pos.e0]=ll(canvskewer(pos));
		dp_horiz[pos.e1][pos.e0]=ll(canhskewer(pos));
		dp_no[pos.e1][pos.e0]=0;

		pll oldpos = pos;
		pos.e0-=1;
		pos.e1+=1;
		while (inrange(pos)) {

			dp_no[pos.e1][pos.e0] = max({
				dp_vert[oldpos.e1][oldpos.e0]
				,dp_horiz[oldpos.e1][oldpos.e0] 
				,dp_no[oldpos.e1][oldpos.e0]
			});

			dp_vert[pos.e1][pos.e0] = canvskewer(pos) + max({
				dp_vert[oldpos.e1][oldpos.e0]
				,dp_no[oldpos.e1][oldpos.e0]
			});

			dp_horiz[pos.e1][pos.e0] = canhskewer(pos) + max({
				dp_horiz[oldpos.e1][oldpos.e0]
				,dp_no[oldpos.e1][oldpos.e0]
			});


			oldpos = pos;
			pos.e0-=1;
			pos.e1+=1;
		}

		outp+=max({
				dp_vert[oldpos.e1][oldpos.e0]
				,dp_horiz[oldpos.e1][oldpos.e0] 
				,dp_no[oldpos.e1][oldpos.e0]
			});
		dbgv(d << ":" << outp);
	}

	cout << outp;

}

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