Submission #1289622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289622		dirtblock	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	119 ms	10380 KiB

dango_maker

#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;
}

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