Submission #666756

#	Time	Username	Problem	Language	Result	Execution time	Memory
666756		manizare	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	799 ms	133028 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 =1e5 , inf = 1e9 + 100 , mod = 1e9 + 7 ;
char c[maxn][maxn] ;
vector <int> G[maxq] ;
vector <pair <int , int > > vec[maxq] ;
int ans[2] ;
int dp[maxq][3] ;
bool mark[maxq] , u[maxn][maxn]  , t[maxn][maxn];
void dfs(int v , int k){
	mark[v] = 1;
	ans[k]++;
	for(int i = 0 ; i < (int)G[v].size() ; i++){
		int u = G[v][i] ;
		if(mark[u] == 1)continue ;
		dfs(u , k^1);  
	}
}
 
signed main(){
	int n , m ;
	cin >> n >> m ;
	for(int i = 1; i <= n ; i++){
		for(int j = 1; j <= m ; j++){
			cin >> c[i][j] ;
		}
	}
	int cnt = 0 ;
	for(int i =1 ; i <= n ; i++){
		for(int j = 1; j <= m ; j++){
			vec[i+j].pb({i,j});
			if(i <= (n-2) && c[i][j] == 'R' && c[i+1][j] == 'G' && c[i+2][j] == 'W'){
				t[i][j] = 1;
			}
			if(j <= (m-2) && c[i][j] == 'R' && c[i][j+1] == 'G' && c[i][j+2] == 'W'){
				u[i][j] = 1 ;
			}
		}
	}
	int ans1 = 0 ;
	for(int i =  2; i <= (n+m) ; i++){
		for(int j = 1 ; j <= vec[i].size() ; j++){
			int x = vec[i][j-1].first , y = vec[i][j-1].second ;
			dp[j][0] = max(dp[j-1][0] , max(dp[j-1][1] , dp[j-1][2]));
			dp[j][1] = dp[j][2] = 0 ;
			if(u[x][y] == 1){
				dp[j][1] = 1 + max(dp[j-1][1] , (j == 1 ? 0 : max(dp[j-2][1] , dp[j-2][0])));                           			
			}
			if(t[x][y] == 1){
				dp[j][2] = 1 + max(dp[j-1][0] , max(dp[j-1][1] , dp[j-1][2]));
			}
		}
		int j = vec[i].size() ; 
		ans1 += max(dp[j][0] , max(dp[j][1] , dp[j][2]));
	}
	cout << ans1 << "\n";
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int j = 1 ; j <= vec[i].size() ; j++){
      |                   ~~^~~~~~~~~~~~~~~~
dango_maker.cpp:30:6: warning: unused variable 'cnt' [-Wunused-variable]
   30 |  int cnt = 0 ;
      |      ^~~

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