Submission #1113774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113774		Dan4Life	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	252 ms	19024 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int N = (int)3e3+2;
int n, m;
string s[N];

int calc(int i, int j){
	int x = i, y = j;
	vector<array<int,2>> v; v.clear(); v.pb({x,y});
	while(x+1<n and y) x++, y--, v.pb({x,y});
	reverse(all(v)); int dp[sz(v)+1][3];
	for(int i = 0; i <= sz(v); i++) 
		for(int j = 0; j < 3; j++) dp[i][j]=-N*N;
	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	for(i = 1; i <= sz(v); i++){
		dp[i][0] = max({dp[i-1][0],dp[i-1][1],dp[i-1][2]});
		auto [x,y] = v[i-1];
		if(s[x][y]==3 or s[x][y]==1){
			dp[i][1] = max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+1;
		}
		if(s[x][y]==3 or s[x][y]==2){
			dp[i][2] = dp[i-1][2]+1;
			if(i>=2) dp[i][2] = max(dp[i][2], max(dp[i-2][0],dp[i-2][2])+1);
		}
	}
	return max({dp[sz(v)][0],dp[sz(v)][1],dp[sz(v)][2]});
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> s[i];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(s[i][j]!='R') continue;
			bool ok1 = 0, ok2 = 0;
			if(j+2<m and s[i][j+1]=='G' and s[i][j+2]=='W') ok1=1;
			if(i+2<n and s[i+1][j]=='G' and s[i+2][j]=='W') ok2=1;
			s[i][j] = ok2*2+ok1;
		}
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(s[i][j]=='G' or s[i][j]=='W') s[i][j]=0;
	int ans = 0;
	for(int j = 0; j < m; j++) ans+=calc(0,j);
	for(int i = 1; i < n; i++) ans+=calc(i,m-1);
	cout << ans << "\n";
}

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