Submission #522368

#	Time	Username	Problem	Language	Result	Execution time	Memory
522368		AdamGS	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	145 ms	89492 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e3+7;
string T[LIM];
int ok[LIM][LIM], odw[LIM][LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	rep(i, n) cin >> T[i];
	rep(i, n) rep(j, m) if(T[i][j]=='G') {
		if(i && i<n-1 && T[i-1][j]=='R' && T[i+1][j]=='W') ok[i][j]|=1;
		if(j && j<m-1 && T[i][j-1]=='R' && T[i][j+1]=='W') ok[i][j]|=2;
	}
	int ans=0;
	rep(i, n) rep(j, m) if(ok[i][j] && !odw[i][j]) {
		odw[i][j]=1;
		int dp[2][3];
		dp[1][0]=dp[1][1]=dp[1][2]=0;
		if(ok[i][j]&1) ++dp[1][1];
		if(ok[i][j]&2) ++dp[1][2];
		int a=i, b=j;
		while(a<n-1) {
			++a;
			if(b && (ok[a-1][b]|ok[a][b-1])==3) --b;
			else if(b<m-1 && (ok[a-1][b]|ok[a][b+1])==3) ++b;
			else break;
			odw[a][b]=1;
			rep(l, 3) {
				dp[0][l]=dp[1][l];
				dp[1][l]=0;
			}
			dp[1][0]=max(dp[0][0], max(dp[0][1], dp[0][2]));
			if(ok[a][b]&1) dp[1][1]=max(dp[0][0], dp[0][1])+1;
			if(ok[a][b]&2) dp[1][2]=max(dp[0][0], dp[0][2])+1;
		}
		ans+=max(dp[1][0], max(dp[1][1], dp[1][2]));
	}
	cout << ans << '\n';
}

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