Submission #535113

#	Time	Username	Problem	Language	Result	Execution time	Memory
535113		amunduzbaev	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	266 ms	68728 KiB

dango_maker

#include "bits/stdc++.h"
using namespace std;

#define ar array

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<string> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	vector<vector<int>> in(n + m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			in[i + j].push_back(i);
		}
	}
	
	auto can = [&](int i, int j){
		return (0 < j && j+1 < m && a[i][j-1] == 'R' && a[i][j] == 'G' && a[i][j+1] == 'W');
	};
	
	auto can_ = [&](int i, int j){
		return (0 < i && i+1 < n && a[i-1][j] == 'R' && a[i][j] == 'G' && a[i+1][j] == 'W');
	};
	
	int res = 0;
	for(int s=0;s<n+m;s++){
		int k = in[s].size();
		vector<ar<int, 3>> dp(k + 1);
		for(int l=1;l<=k;l++){
			int i = in[s][l-1], j = s - i;
			dp[l][0] = max({dp[l-1][0], dp[l-1][1], dp[l-1][2]});
			if(can(i, j)) dp[l][1] = max(dp[l-1][0], dp[l-1][1]) + 1;
			if(can_(i, j)) dp[l][2] = max(dp[l-1][0], dp[l-1][2]) + 1;
		}
		
		res += max({dp[k][0], dp[k][1], dp[k][2]});
		//~ cout<<s<<" "<<dp[k][0]<<"\n";
	}
	
	cout<<res<<"\n";
}

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