제출 #1289622

#제출 시각아이디문제언어결과실행 시간메모리
1289622dirtblockDango Maker (JOI18_dango_maker)C++20
100 / 100
119 ms10380 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

bool check(int i,int j,char c,int n,int m,vector<string> &s) {
	return (i>=0&&j>=0&&i<n&&j<m&&c==s[i][j]);
}

signed main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n,m; cin>>n>>m;
	vector<string> s(n);
	for(int i=0; i<n; i++) cin>>s[i];
	vector<array<int,3>> dp(n+m+1);
	int ans=0;
	for(int g=0; g<n+m; g++) {
		for(int i=0; i<=g; i++) {
			dp[i+1][0]=max({dp[i][0],dp[i][1],dp[i][2]});
			dp[i+1][1]=max(dp[i][0],dp[i][1])+(check(i,g-i,'G',n,m,s)&&check(i-1,g-i,'R',n,m,s)&&check(i+1,g-i,'W',n,m,s));
			dp[i+1][2]=max(dp[i][0],dp[i][2])+(check(i,g-i,'G',n,m,s)&&check(i,g-i-1,'R',n,m,s)&&check(i,g-i+1,'W',n,m,s));
		}
		ans+=max({dp[g+1][0],dp[g+1][1],dp[g+1][2]});
	}
	cout<<ans;
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...