제출 #376559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376559		astoria	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	399 ms	53868 KiB

dango_maker

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

const int N=3005,M=3005;
//vector<pair<pair<int,int>,int> > g[N][M][2]; //j=0,i=1;
bool is[N][M][2];
bool vis[N][M][2];

pair<int,int> dfs(int x, int y, int k){ //first = dp at this level, second = dp at below level.
	if(vis[x][y][k]) return {0,0};
	vis[x][y][k] = 1;
	
	pair<int,int> an={0,0};
	
	int tk;
	if(k==0) tk=1;
	else tk=0;
	
	if(is[x][y][tk]){
		pair<int,int> their = dfs(x,y,tk);
		an.first += their.first; an.second += their.second;
	}
	if(is[x-1][y+1][tk]){
		pair<int,int> their = dfs(x-1,y+1,tk);
		an.first += their.first; an.second += their.second;
	}
	if(is[x+1][y-1][tk]){
		pair<int,int> their = dfs(x+1,y-1,tk);
		an.first += their.first; an.second += their.second;
	}
	
	pair<int,int> ret;
	ret.second = an.first; //dp at below level
	ret.first = max(an.second+1,an.first);
	return ret;
	
	/*pair<int,int> an;
	if(k==0) an={1,0};
	else an={0,1};
	for(auto ii : g[x][y][k]){
		pair<int,int> their = dfs(ii.first.first,ii.first.second,ii.second);
		an.first += their.first; an.second += their.second;
	}
	return an;*/
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	char grid[n+5][m+5];
	
	for(int i=0; i<=n+1; i++){
		for(int j=0; j<=m+1; j++){
			grid[i][j]='p';
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>grid[i][j];
		}
	}
	
	
	memset(is,0,sizeof(is));
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(grid[i][j]!='G') continue;
			
			if(grid[i][j-1]=='R'&&grid[i][j+1]=='W'){
				is[i][j][0]=1;
			}
			if(grid[i-1][j]=='R'&&grid[i+1][j]=='W'){
				is[i][j][1]=1;
			}
		}
	}
	/*
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(!is[i][j][0]) continue;
			if(is[i][j][1]){
				g[i][j][0].push_back({{i,j},1});
			}
			if(is[i-1][j+1][1]){
				g[i][j][0].push_back({{i-1,j+1},1});
			}
			if(is[i+1][j-1][1]){
				g[i][j][0].push_back({{i+1,j-1},1});
			}
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(!is[i][j][1]) continue;
			if(is[i][j][0]){
				g[i][j][1].push_back({{i,j},0});
			}
			if(is[i-1][j+1][0]){
				g[i][j][1].push_back({{i-1,j+1},0});
			}
			if(is[i+1][j-1][0]){
				g[i][j][1].push_back({{i+1,j-1},0});
			}
		}
	}*/
	//cout<<"HEY"<<endl;
	memset(vis,0,sizeof(vis));
	int tot=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(is[i][j][0]&&!vis[i][j][0]){
				pair<int,int> an = dfs(i,j,0);
				tot += max(an.first,an.second);
			}
			if(is[i][j][1]&&!vis[i][j][1]){
				pair<int,int> an = dfs(i,j,1);
				tot += max(an.first,an.second);
			}
		}
	}
	
	cout<<tot;
}

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