Submission #82081

#	Time	Username	Problem	Language	Result	Execution time	Memory
82081		wzy	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	771 ms	218112 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
char s[3003][3003];
int n , m;
int ans = 0;
bool can[2][3003][3003];
int dp[3003][3003][3];
int32_t main(){
	scanf("%d%d" , &n , &m);
	for(int i = 0 ; i  < n; i ++)
		for(int j = 0 ; j < m ; j ++) scanf(" %c" , &s[i][j]);
	for(int i = 0 ; i < n; i++){
		for(int j = 0 ; j < m ;j ++){
			if(s[i][j] == 'G'){
				if((j+1) < m && s[i][j+1] == 'W' && (j-1) >= 0 && s[i][j-1] == 'R') can[0][i][j] = true;
				if((i+1) < n && s[i+1][j] == 'W' && (i-1) >= 0 && s[i-1][j] == 'R') can[1][i][j] = true; 
			}
		}
	}
	for(int i = n-1 ; i >= 0 ; i--){
		for(int j = 0 ; j < m; j ++){
				dp[i][j][1] = can[0][i][j];
				dp[i][j][2] = can[1][i][j];
				if((i+1) < n && (j-1) >= 0){
					dp[i][j][0] = max(dp[i+1][j-1][0] , max(dp[i+1][j-1][1] , dp[i+1][j-1][2]));
					dp[i][j][1] = max(dp[i+1][j-1][1] , dp[i+1][j-1][0]) + (can[0][i][j]);
					dp[i][j][2] = max(dp[i+1][j-1][2] , dp[i+1][j-1][0]) + (can[1][i][j]);
				}
			
		}
	}
	int ans = 0;
	
	for(int i = 0 ; i < m; i ++){
		pair<int,int> curr = pair<int,int>(0 , i);
		ans += max(dp[curr.F][curr.S][0] , max(dp[curr.F][curr.S][1] , dp[curr.F][curr.S][2]));
	}
	for(int j = 0 ; j < n ; j ++){
		pair<int,int> curr = pair<int,int>(j , m-1);
		ans += max(dp[curr.F][curr.S][0] , max(dp[curr.F][curr.S][1] , dp[curr.F][curr.S][2]));
	}
	pair<int,int> curr = pair<int,int>(0 , m-1);
	ans -= max(dp[curr.F][curr.S][0] , max(dp[curr.F][curr.S][1] , dp[curr.F][curr.S][2]));
	printf("%d\n" , ans);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int32_t main()':
dango_maker.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n , &m);
  ~~~~~^~~~~~~~~~~~~~~~~~
dango_maker.cpp:13:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int j = 0 ; j < m ; j ++) scanf(" %c" , &s[i][j]);
                                 ~~~~~^~~~~~~~~~~~~~~~~~

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