Submission #1162717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162717		elotelo966	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	0 ms	328 KiB

dango_maker

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

#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define pb push_back
#define lim 305

int n,m,cev,maxi,cur1,cur2;

char dizi[lim][lim];

int vis[lim][lim][2],dp[lim][lim][2];

vector<pair<int,int>> sol,ust;

inline int ind(int x,int y,int z){
	return n*m*z+(x-1)*m+y;
}

inline bool check(int x,int y){
    return x>=1 && x<=n && y>=1 && y<=m;
}

inline bool check_left(int x,int y){
	return check(x,y) && check(x,y+1) && check(x,y+2) && dizi[x][y]=='R' && dizi[x][y+1]=='G' && dizi[x][y+2]=='W';
}

inline bool check_top(int x,int y){
	return check(x,y) && check(x+1,y) && check(x+2,y) && dizi[x][y]=='R' && dizi[x+1][y]=='G' && dizi[x+2][y]=='W';
}

inline int f(int pl,int pu,int kim){
	if(~dp[pl][pu][kim])return dp[pl][pu][kim];
	int cur=0;
	if(kim){
		for(int i=pl;i<sol.size();i++){
			if(sol[i].fi<=ust[pu].fi+2)continue;
			cur=max(cur,f(i,pu,0)+1);
			break;
		}
		if(pu+1<ust.size())cur=max(cur,f(pl,pu+1,1)+1);
	}
	else{
		for(int i=pu;i<ust.size();i++){
			if(ust[i].fi<=sol[pl].fi)continue;
			cur=max(cur,f(pl,i,1)+1);
		}
		if(pl+1<sol.size())cur=max(cur,f(pl+1,pu,0)+1);
	}
	return dp[pl][pu][kim]=cur;
}

int32_t main(){
	faster
	cin>>n>>m;
	FOR{
		string s;cin>>s;
		for(int j=0;j<m;j++){
			dizi[i][j+1]=s[j];
		}
	}
	
	FOR{
		for(int j=1;j<=m;j++){
            if(vis[i][j][0] || vis[i][j][1])continue;
            sol.clear();
            ust.clear();
            queue<pair<int,pair<int,int>>> q;
			if(check_left(i,j)){
                q.push({i,{j,0}});
            }
            if(check_top(i,j)){
                q.push({i,{j,1}});
            }

            while(q.size()){
                int l=q.front().fi,r=q.front().se.fi,kim=q.front().se.se;
                q.pop();
                if(vis[l][r][kim])continue;
                vis[l][r][kim]=1;
                if(kim){
                    if(check_left(l,r))q.push({l,{r,0}});
                    if(check_left(l+1,r-1))q.push({l+1,{r-1,0}});
                    if(check_left(l+2,r-2))q.push({l+2,{r-2,0}});
                    ust.pb({l,r});
                }
                else{
                    if(check_top(l,r))q.push({l,{r,1}});
                    sol.pb({l,r});
                }
            }

            //~ reverse(sol.begin(),sol.end());

            //~ reverse(ust.begin(),ust.end());
            
            //~ cout<<i<<" ->  "<<j<<endl;

            //~ for(auto a:sol)cout<<a.fi<<" "<<a.se<<endl;
            //~ cout<<endl;

            //~ for(auto a:ust)cout<<a.fi<<" "<<a.se<<endl;
            //~ cout<<endl;
            
            for(int i=0;i<sol.size();i++){
				for(int j=0;j<ust.size();j++){
					dp[i][j][0]=dp[i][j][1]=-1;
				}
			}
			
			int cur_ans=0;
						
            if(sol.size())cur_ans=max(cur_ans,f(0,0,0)+1);
            //cout<<cur_ans<<endl;
            if(ust.size())cur_ans=max(cur_ans,f(0,0,1)+1);
            
           // cout<<cur_ans<<endl;
            
            
            cev+=cur_ans;
            
            for(int i=0;i<sol.size();i++){
				for(int j=0;j<ust.size();j++){
					dp[i][j][0]=dp[i][j][1]=-1;
				}
			}

		}
	}
	
	cout<<cev<<'\n';
	
	return 0;
}

/*
 * 
 * 
RRRR
RRGW
RGWR
RGWW

*/

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