Submission #1328022

#TimeUsernameProblemLanguageResultExecution timeMemory
1328022jumpDango Maker (JOI18_dango_maker)C++20
100 / 100
283 ms247240 KiB
#include <bits/stdc++.h>
#define int long long
int dp[3001][3001][3];
bool dango[3001][3001][2];
signed main() {
	int n,m;
	std::cin >> n >> m;
	std::vector<std::string> grid;
	std::string dummy;
	for(int i=0;i<=m;i++)dummy.push_back('X');
	grid.push_back(dummy);
	for(int i=0;i<n;i++){
		std::string s;
		std::cin >> s;
		grid.push_back("X"+s+"X");
	}
	grid.push_back(dummy);
	int best = 0;
	for(int i=1;i<=n;i++){
		for(int j=m;j>0;j--){
			if(grid[i][j]=='G'&&grid[i][j-1]=='R'&&grid[i][j+1]=='W')dango[i][j][0]=true;
			if(grid[i][j]=='G'&&grid[i-1][j]=='R'&&grid[i+1][j]=='W')dango[i][j][1]=true;
			dp[i][j][0] = dp[i-1][j+1][0];
			dp[i][j][0] = std::max(dp[i][j][0],dp[i-1][j+1][1]);
			dp[i][j][0] = std::max(dp[i][j][0],dp[i-1][j+1][2]);
			if(dango[i][j][0])
			dp[i][j][1] = dp[i-1][j+1][0]+1;
			if(dango[i][j][0])
			dp[i][j][1] = std::max(dp[i][j][1],dp[i-1][j+1][1]+1);
			if(dango[i][j][1])
			dp[i][j][2] = dp[i-1][j+1][0]+1;
			if(dango[i][j][1])
			dp[i][j][2] = std::max(dp[i][j][2],dp[i-1][j+1][2]+1);
		}
	}
	// for(int i=1;i<=n;i++){
	// 	for(int j=1;j<=m;j++){
	// 		std::cout << dp[i][j][0] << '|' << dp[i][j][1] << '|' << dp[i][j][2] << ' ';
	// 	}std::cout <<  '\n';
	// }
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=std::max(dp[i][1][0],std::max(dp[i][1][1],dp[i][1][2]));
	}
	//std::cout << sum << '\n';
	for(int j=1;j<=m;j++){
		sum+=std::max(dp[n][j][0],std::max(dp[n][j][1],dp[n][j][2]));
	}
	//std::cout << sum << '\n';
	sum-=std::max(dp[n][1][0],std::max(dp[n][1][1],dp[n][1][2]));
	std::cout << sum;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...