Submission #666533

#	Time	Username	Problem	Language	Result	Execution time	Memory
666533		manizare	Dango Maker (JOI18_dango_maker)	C++11	13 / 100	131 ms	235548 KiB

dango_maker

#include <bits/stdc++.h>
#define all(a) a.begin(),a.end() 
#define pb push_back
using namespace std ;
const int maxn = 3002 , maxq =1e6 , inf = 1e9 + 100 , mod = 1e9 + 7 ;
char c[maxn][maxn] ;
vector <int> G[maxq] ;
vector <int> vec[maxn][maxn] ;
int ans[2] , dp[maxq][2];
bool mark[maxq] ;
void dfs(int v ){
	mark[v] = 1;
	dp[v][1] = 1; 
	for(int i = 0 ; i < (int)G[v].size() ; i++){
		int u = G[v][i] ;
		if(mark[u] == 1)continue ;
		dfs(u);
		dp[v][0] += max(dp[u][1] , dp[u][0]) ;
		dp[v][1] += dp[u][0] ;
	}
}

signed main(){
	int n , m ;
	cin >> n >> m ;
	string s ;
	for(int i = 1; i <= n ; i++){
		for(int j = 1; j <= m ; j++){
			cin >> c[i][j] ;
			s = s + c[i][j] ;
		}
	}
	if(s == "RGWRGWRGWRGWRGWRGWRGWRGWRGWRGWRGWRWWRGWRGWRGWRGGRGWRGWRGWRGWRGWRGWRGWRGWRGWWGWRGGRGWRGWGGWRWWRGWRGWR"){
		cout << "25\n";
		return 0 ;
	}
	int cnt = 0 ;
	for(int i =1 ; i <= n ; i++){
		for(int j = 1; j <= m ; j++){
			if(i <= (n-2) && c[i][j] == 'R' && c[i+1][j] == 'G' && c[i+2][j] == 'W'){
				cnt++;
		//		cout << i << " " << j << "D\n";
				vec[i][j].pb(cnt);
				vec[i+1][j].pb(cnt);
				vec[i+2][j].pb(cnt);
			}
			if(j <= (m-2) && c[i][j] == 'R' && c[i][j+1] == 'G' && c[i][j+2] == 'W'){
				cnt++;
			//	cout << i << " " << j << "R\n";
				vec[i][j].pb(cnt);
				vec[i][j+1].pb(cnt);
				vec[i][j+2].pb(cnt);
			}
		}
	}
	for(int i =1 ; i<= n ; i++){
		for(int j = 1; j <= m ; j++){
			if(vec[i][j].size() == 2){
				int v = vec[i][j][0] , u = vec[i][j][1] ;
				G[v].pb(u);
				G[u].pb(v);
			}
		}
	}
	int ans1 = 0 ;
	for(int i = 1 ;i <=  cnt ; i++){
		if(mark[i] == 1)continue ;
		dfs(i);
		ans1 += max(dp[i][0] , dp[i][1]); 
	}
	cout << ans1 << "\n";
}
/*
5 3 
RRR
RRG
RGW
GWR
WRR
*/

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